You are assigned to put some amount of boxes onto one truck. You are given a 2D vector of box_types
where box_type[0] is the number of a type of box and box_type[1] is the units per box for that type. You are also given an integer value for the truck size, this the maximum boxes you can put in the truck. Return the maximum unit that can be put in a given truck.
Example
input : box_types = {{1, 3}, {2, 2}, {3, 1}} truck_size = 4
output: 8
Explanation:
There are
- 1 box of type 0
- 2 box of type 1
- 3 box of type 2
where 0, 1, 2 is the index of the vector
You can take all the boxes of the first type, second type and one box from the third type
max_unit = (1 * 3) + (2 * 2) + (1 * 1) = 8
Here is my implementation
#include <iostream>
#include <algorithm>
#include <vector>
void sort_boxtypes(std::vector<std::vector<int>> &box_types)
{
std::sort(
box_types.begin(), box_types.end(),
[](const std::vector<int>& a, const std::vector<int> &b)
{return a[1] > b[1]; }
);
}
int maximum_units(std::vector<std::vector<int>> box_types, int truck_size)
{
sort_boxtypes(box_types);
int max_unit = 0;
for(const auto& box_type : box_types)
{
truck_size -= box_type[0];
if(truck_size >= 0)
max_unit += box_type[0] * box_type[1];
else
{
max_unit += (box_type[0] + truck_size) * box_type[1];
return max_unit;
}
}
return max_unit;
}
int main()
{
std::vector<std::vector<int>> box_types = {{5, 10}, {2, 5}, {4, 7}, {3, 9}};
int max = maximum_units(box_types, 10);
std::cout << max << '\n';
}