Cargo bike manifest
MediumOnline Assessment
Decide what a courier should load onto a cargo bike.
The depot has several kinds of parcel. boxes[i] = [weight, fee, stock] says that every parcel of kind i weighs weight kg, pays fee for delivery, and that the depot has stock such parcels available. The bike can carry at most capacity kg in total. The courier may take any number of parcels of each kind, from 0 up to its stock, and wants the largest total fee.
Several loads can pay the same maximum fee. The courier would rather ride light, so among the loads with the maximum fee, pick the one with the smallest total weight.
Input: boxes, a list of [weight, fee, stock], and capacity.
Output: a two-element list [bestFee, weight]: the largest total fee, and the smallest total weight of any load that earns it. An empty load earns [0, 0], which is the answer when nothing fits or boxes is empty. A kind with a stock of 0, or a weight above capacity, can never be loaded.
Stocks can be enormous (up to 10^9), so putting every parcel on its own row of a table and trying them one by one is far too slow.
Example 1
- Input:
- [[[3,5,2],[4,6,3]],10]
- Output:
- [16,10]
- Explanation
- Capacity 10. Kind 0 weighs 3 and pays 5 (2 in stock); kind 1 weighs 4 and pays 6 (3 in stock). Both of kind 0 and one of kind 1 weigh 10 and pay 16. Two of kind 1 plus one of kind 0 pay 17 but weigh 11, too heavy, and two of kind 1 alone weigh 8 and pay only 12. The best fee is 16 at weight 10, so the answer is
[16, 10].
Example 2
- Input:
- [[[3,4,2],[5,4,1]],8]
- Output:
- [8,6]
- Explanation
- Capacity 8. Kind 0 weighs 3 and pays 4 (2 in stock); kind 1 weighs 5 and pays 4 (1 in stock). Carrying one of each weighs 8 and pays 8, but carrying both of kind 0 also pays 8 and weighs only 6. Among loads with the maximum fee 8 the lightest has weight 6, so the answer is
[8, 6].
Example 3
- Input:
- [[[4,9,1000000000],[1,1,1]],10]
- Output:
- [19,9]
- Explanation
- Capacity 10 with a huge stock of weight-4 parcels paying 9, and a single weight-1 parcel paying 1. Two heavy parcels weigh 8 and pay 18, and adding the light one weighs 9 and pays 19. A third heavy parcel would not fit. The answer is
[19, 9]; the capacity, not the stock, is the limit.
Constraints
0 <= boxes.length <= 201 <= weight <= 2,000,1 <= fee <= 1,000,000,0 <= stock <= 1,000,000,0000 <= capacity <= 2,000