贪心算法——卡车上的最大单元数（LeetCode-1710）_C

1. 问题描述：

请你将一些箱子装在一辆卡车上。

给你一个二维数组 boxTypes ，其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：
numberOfBoxesi 是类型 i 的箱子的数量。

numberOfUnitsPerBoxi 是类型 i 每个箱子可以装载的单元数量。

整数 truckSize 表示卡车上可以装载箱子的最大数量。

只要箱子数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。

返回卡车可以装载单元的最大总数。

2. 示例：示例 1：

输入：boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
输出：8
解释：箱子的情况如下：

1 个第一类的箱子，里面含 3 个单元。
2 个第二类的箱子，每个里面含 2 个单元。
3 个第三类的箱子，每个里面含 1 个单元。

可以选择第一类和第二类的所有箱子，以及第三类的一个箱子。

单元总数 = (1 * 3) + (2 * 2) + (1 * 1) = 8

示例 2：

输入：boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
输出：91

3. 题解：

本题采用贪心的思想，要让卡车上装载的单元数量最大，在卡车上可以装载箱子的最大数量限制下，就要优先选取装载的单元数量多的箱子。

箱子按照每个箱子可以装载的单元数量从大到小排序，在 truckSize 限制下贪心选取容量大的箱子。

使用贪心算法一定要给予证明，这是因为贪心算法不一定能得到最优解，贪心（greedy）也就是每一步都选取当前局部最优的策略，但是不能保证全局最优，下面是简单的证明过程：
设最大装载数量为S，箱子的容量分别为k1,k2,k3···（降序）
（1）全局最优解一定包含k1
证明：【反证法】假如全局最优解不包含容量最大的k1，即另存在一个比我更优的解，那么我们将这个优化解中的最大容量的箱子更换成k1，那么得到的解一定 >= 这个优化解
（2）考虑 S - [k1]，即已选择最大容量箱子之后的子问题，那么这个子问题一定包含 S - [k1] 中容量最大的箱子。

证明：思路同上
（3）根据以上两条引理，就可以发现全局最优解即为每一步均选取容量最大的箱子得到的优化解。

4. 代码：

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