Greedy Algorithm to Put Maximum Units on a Truck

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:

numberOfBoxesi is the number of boxes of type i.
numberOfUnitsPerBoxi is the number of units in each box of the type i.
You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.

Example 1:
Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
Explanation: There are:
– 1 box of the first type that contains 3 units.
– 2 boxes of the second type that contain 2 units each.
– 3 boxes of the third type that contain 1 unit each.
You can take all the boxes of the first and second types, and one box of the third type.
The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.

Example 2:
Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91

Constraints:
1 <= boxTypes.length <= 1000
1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
1 <= truckSize <= 106

Hints:
If we have space for at least one box, it’s always optimal to put the box with the most units.
Sort the box types with the number of units per box non-increasingly.
Iterate on the box types and take from each type as many as you can.

Greedy Algorithm (Knapsack Problem)

This is one special type of the Knapsack problem where we can use the Greedy Algorithm to solve this. Givne One Knapsack (Truck) with Size truckSize, and there are N types of boxes (items) each box (item) has its value (unit), we want to maximum the number of items to put in the truck. Each item has same weight (cost is 1).

Optimally, we want to pick the box that has the most units first, therefore we can sort it and simulate the process by putting 1 box at a time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        sort(begin(boxTypes), end(boxTypes), [](auto &a, auto &b) {
            return a[1] < b[1];
        });
        int ans = 0;
        int a = boxTypes.size() - 1;
        while (truckSize > 0) {            
            ans += boxTypes[a][1];
            truckSize --;
            if (--boxTypes[a][0] == 0) {
                a --;
                if (a < 0) break;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        sort(begin(boxTypes), end(boxTypes), [](auto &a, auto &b) {
            return a[1] < b[1];
        });
        int ans = 0;
        int a = boxTypes.size() - 1;
        while (truckSize > 0) {            
            ans += boxTypes[a][1];
            truckSize --;
            if (--boxTypes[a][0] == 0) {
                a --;
                if (a < 0) break;
            }
        }
        return ans;
    }
};

We can do better by putting M boxes (which is the minimal of truck size and the current box type), this will be faster:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        sort(begin(boxTypes), end(boxTypes), [](auto &a, auto &b) {
            return a[1] > b[1];
        });
        int ans = 0;
        int a = 0;
        while ((a < boxTypes.size()) && (truckSize > 0)) {
            int m = min(truckSize, boxTypes[a][0]);
            ans += boxTypes[a][1] * m;
            truckSize -= m;
            a ++;
        }
        return ans;
    }
};

class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        sort(begin(boxTypes), end(boxTypes), [](auto &a, auto &b) {
            return a[1] > b[1];
        });
        int ans = 0;
        int a = 0;
        while ((a < boxTypes.size()) && (truckSize > 0)) {
            int m = min(truckSize, boxTypes[a][0]);
            ans += boxTypes[a][1] * m;
            truckSize -= m;
            a ++;
        }
        return ans;
    }
};

Also, we can do this by using a priority queue. So that each time we deque a box which will be the current box with the most unit:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        auto cmp = [&](auto &a, auto &b) {
            return boxTypes[a][1] < boxTypes[b][1];
        };
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
        for (int i = 0; i < boxTypes.size(); ++ i) {
            pq.push(i);
        }
        int ans = 0;
        while (!pq.empty() && (truckSize > 0)) {
            auto b = pq.top();
            pq.pop();
            auto m = min(truckSize, boxTypes[b][0]);
            truckSize -= m;
            ans += m * boxTypes[b][1];
        }
        return ans;
    }
};

class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        auto cmp = [&](auto &a, auto &b) {
            return boxTypes[a][1] < boxTypes[b][1];
        };
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
        for (int i = 0; i < boxTypes.size(); ++ i) {
            pq.push(i);
        }
        int ans = 0;
        while (!pq.empty() && (truckSize > 0)) {
            auto b = pq.top();
            pq.pop();
            auto m = min(truckSize, boxTypes[b][0]);
            truckSize -= m;
            ans += m * boxTypes[b][1];
        }
        return ans;
    }
};

All implementations are O(N LogN) time. The first two are O(1) constant space and the last approach will cost O(N) space due to the priority queue.

–EOF (The Ultimate Computing & Technology Blog)