Maximum Units on a Truck

Problem Statement

In this problem, you are tasked with determining how to optimally load boxes onto a single truck based on unit containment. You are provided with a 2D array boxTypes, where each inner array boxTypes[i] includes:

• numberOfBoxesi - indicating the quantity of boxes of type i.
• numberOfUnitsPerBoxi - representing the number of units held by each box of type i.

You are also given an integer truckSize, which represents the maximum capacity of the truck in terms of the number of boxes it can carry. The goal is to maximize the total number of units loaded on the truck without exceeding its box capacity (truckSize). To solve this problem, you are required to determine the optimal combination of boxes, maximizing unit count, while respecting the truck's box carrying capacity.

Examples

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

Approach and Intuition

To tackle the maximum units on a truck problem, the natural approach revolves around efficiently using the truck's capacity with boxes that have the highest unit per box ratio. Here's a straightforward walkthrough to derive a solution:

1. Sort the list of boxTypes based on the number of units per box in decreasing order. This enables prioritization of box types that can maximize units on the truck.
2. Initialize a counter for total units (totalUnits) and another to keep track of the accumulated box count on the truck (usedCapacity).
3. Iterate through the sorted list. For each type of box, calculate how many boxes you can load onto the truck without exceeding the truckSize.
   • If the sum of usedCapacity and the boxes of the current type (numberOfBoxesi) is less than or equal to truckSize, add all boxes of that type. The corresponding units are added after calculating the product of the number of boxes and units per box.
   • If adding all boxes of the current type would exceed truckSize, only add as many boxes as you can fit. Calculate the added units correspondingly.
4. Add the resultant units to totalUnits and adjust usedCapacity.
5. If the truckSize is filled, break out of the loop as no more boxes can be added.
6. Return the total units calculated, which represents the maximum units that can be loaded onto the truck given the constraints.

This approach makes sure that the most valuable boxes in terms of unit content are considered first, ensuring that the space on the truck is used most efficiently to achieve the maximum number of units.

Solutions

class Solution {
public:
    int maxUnits(vector<vector<int>>& boxTypes, int truckSize) {
        priority_queue<vector<int>, vector<vector<int>>, CompareUnits> pq;
        for (auto type : boxTypes) {
            pq.push(type);
        }
        int totalCount = 0;
        while (!pq.empty()) {
            vector<int> current = pq.top();
            pq.pop();
            int count = min(truckSize, current[0]);
            totalCount += count * current[1];
            truckSize -= count;
            if(truckSize == 0)
                break;
        }
        return totalCount;
    }
    
    struct CompareUnits {
        bool operator()(vector<int> const& a, vector<int> const& b) {
            return a[1] < b[1];
        }
    };
};