[贪心算法]忍者道具
描述
忍者道具有很多种，苦无，飞镖，震爆弹。L君热衷于收集忍者道具，现在他有N个道具，每个道具的重量分别是C1、C2…CN。现在他想把这N个道具装到载重量为W的工具包里，请问他最少需要多少个工具包？
输入
第一行包含两个用空格隔开的整数，N和W。
接下来N行每行一个整数，其中第i+1行的整数表示第i个道具的重量Ci。
输出
输出一个整数，最少需要多少个工具包。
样例输入
5 1996
1
2
1994
12
29
样例输出
2
提示
对于100%的数据，1<=N<=18，1<=Ci<=W<=10^8。
解题分析
这题的话蛮有意思的，因为如果单从思路上入手的话其实题目本身是不难的，可以用递归回溯法，也可以用动态规划的方法。不过实际上这两种方法在测试数据时都容易超时，这题本质上可能需要一种贪心的思维。什么意思呢？首先，我们要明白，要想要使用的工具包最少，那么我们必须最大化我们使用的工具包内部的存储空间，问题的关键就在于，我们怎么去放物品才能最高效地利用背包的空间。这里我们可以思考一下，是谁阻碍了我们使用包包？是那些大的物品！所以我们可能要优先去处理那些比较大的物品。所以，我们读入物品后，对整个物品序列进行一个排序，按照从小到大。然后，这个时候我们去计算一下可能使用的包包最少的数量和最大的数量，接着，我们使用一个循环，在这个循环里面，我们的目标是先放好大的物品，然后再考虑小物品的死活。我们把整个序列最大的物品先扔进一个包里，然后去寻找前面的物品，当找到一个最大的，且可以放入这个包包的物品的时候，我们放入，然后依次这样做，直到我们现在处理的这个包包容量达到最大，那么我们增加我们使用的包的数量。外层的for循环相当于先预支给我们那么多包，然后内层的while循环就在利用预支的这些包进行一个贪心最大化放物品，当我们使用的包超过预支的包的时候，我们就继续多预支一个包，以此类推。
代码实现
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;
int N,W;
vector<int> kits;int findKit(int curSize,int last){if(last==0) return -1;if(kits[last-1]+curSize<=W){return last-1;}if(last==1){return -1;}for(int i=last-2;i>=0;i--){if(curSize+kits[i]<=W && curSize+kits[i+1]>W){return i;}}return -1;
}int main(){scanf("%d%d",&N,&W);kits.resize(N);int totalWeight=0;for(int i=0;i<N;i++){scanf("%d",&kits[i]);totalWeight+=kits[i];}sort(kits.begin(),kits.end());int minBags=totalWeight%W==0?totalWeight/W:totalWeight/W+1;int maxBags=N;int usedBags=0;for(int nBags=minBags;nBags<=maxBags;nBags++){while(usedBags<=nBags){int curSize=0;int last=kits.size()-1;curSize+=kits[last];vector<int> arranged;arranged.push_back(last);while(curSize<=W){int index=findKit(curSize,last);if(index==-1){usedBags++;break;}else{arranged.push_back(index);curSize+=kits[index];last=index;}}int len1=arranged.size();for(int i=0;i<len1;i++){kits.erase(kits.begin()+arranged[i]);}if(kits.size()==0){break;}}if(kits.size()==0){cout<<nBags<<endl;break;}}return 0;
}