Maximum Units on a Truck
给一个2d数组, 第一项是物品个数, 第二项是物品价值, 给一个size, 求满足这个size最大的价值是什么.
看似dp,其实贪婪, 直接排序求即可.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution { public int maximumUnits(int[][] boxTypes, int truckSize) { int res = 0; Arrays.sort(boxTypes,(a,b) -> b[1] - a[1]); for(int[] b : boxTypes) { while(truckSize > 0 && b[0] > 0){ res += b[1]; truckSize--; b[0]--; } } return res; } } |