一道典型的贪心算法题。
题目内容不多说了，大致说一下代码的思路：给定的所有纪念品中可以先用sort排一下顺序，然后从价格最高和最低的开始向中间靠拢（可以看做是指针），这样保证每组的搭配都是最优的。
看代码：
1 #include 2 using namespace std; 3 int w,n,a[100010],b[100010],cnt; 4 int main(){ 5 cin>>w>>n; 6 for(int i=1;i<=n;i++){ 7 cin>>a[i]; 8 b[i]=a[i]; 9 }//设置一个b数组后面用于判断此纪念品是否已被分组 10 sort(a+1,a+n+1);//排序 11 int k=n,m=1;//用k记录剩余未分组的纪念品数量 12 while(k){13 if(b[n]!=0){//这个纪念品还未被分组 14 int sum=a[n];//从最大的开始 15 b[n]=0;//该纪念品已被分组 16 k--;//数量减117 for(int i=m;i<n;i++){//最多查找到当前选定的价格最高的纪念品 18 if(a[i]+sum<=w){//没有超出限制金额 19 sum+=a[i]; //累计纪念品价格 20 b[i]=0;21 k--;22 m++;//下次从这个往上找 23 continue;24 }25 else{26 cnt++;27 break;28 }29 }30 if(k==0){31 cnt++;32 break;33 } 34 //如果没有可以找的了，cnt+1，结束循环，防止上面的循环找到最后没有纪念品 35 }36 n--;//下一次从比这次小得开始。 37 }38 cout<<cnt;39 return 0;40 }