一道典型的贪心算法题。
题目内容不多说了，大致说一下代码的思路：
给定的所有纪念品中可以先用sort排一下顺序，然后从价格最高和最低的开始向中间靠拢（可以看做是指针），这样保证每组的搭配都是最优的。
看代码：
1 #include<bits/stdc++.h>
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--;//数量减1
17 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 }