leetcode 1710. Maximum Units on a Truck（卡车上最大的units)

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.

boxTypes[i] = [这种类型box的数量，这种类型每个box占的unit]，
卡车上最多可放truckSize个box,
问最大可放多少unit

思路：

简单的背包问题，包里最多放truckSize个box, 只限制box的数量，不限制容量，
那当然是先挑unit多的box往里放了，
box按unit排序，先放unit多的，后放少的。

public int maximumUnits(int[][] boxTypes, int truckSize) {
    int res = 0;
    int num = 0;
    Arrays.sort(boxTypes, (a, b)->(b[1] - a[1]));
    
   for(int[] box : boxTypes) {
       if(truckSize <= 0) break;
       
       if(truckSize >= box[0]) res += box[0] * box[1];
       else res += truckSize * box[1];
       
       truckSize -= box[0];
   }
    
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16