Description
农夫约翰要量取 Q（1 <= Q <= 20,000）夸脱（夸脱，quarts，容积单位——译者注） 他的最好的牛奶，并把它装入一个大瓶子中卖出。消费者要多少，他就给多少，从不有任何误差。
农夫约翰总是很节约。他现在在奶牛五金商店购买一些桶，用来从他的巨大的牛奶池中量出 Q
夸脱的牛奶。每个桶的价格一样。你的任务是计算出一个农夫约翰可以购买的最少的桶的集合，使得能够刚好用这些桶量出 Q
夸脱的牛奶。另外，由于农夫约翰必须把这些桶搬回家，对于给出的两个极小桶集合，他会选择“更小的”一个，即：把这两个集合按升序排序，比较第一个桶，选
择第一个桶容积较小的一个。如果第一个桶相同，比较第二个桶，也按上面的方法选择。否则继续这样的工作，直到相比较的两个桶不一致为止。例如，集合
{3，5，7，100} 比集合 {3，6，7，8} 要好。
为了量出牛奶，农夫约翰可以从牛奶池把桶装满，然后倒进瓶子。他决不把瓶子里的牛奶倒出来或者把桶里的牛奶倒到别处。用一个容积为 1 夸脱的桶，农夫约翰可以只用这个桶量出所有可能的夸脱数。其它的桶的组合没有这么方便。
计算需要购买的最佳桶集，保证所有的测试数据都至少有一个解。
Input
Line 1: 一个整数 Q
Line 2: 一个整数P（1 <= P <= 100），表示商店里桶的数量
Lines 3..P+2: 每行包括一个桶的容积（1 <= 桶的容积 <= 10000）
Output
输出只有一行，由空格分开的整数组成：
为了量出想要的夸脱数，需要购买的最少的桶的数量，接着是：一个排好序的列表（从小到大），表示需要购买的每个桶的容积
Sample Input
16 3 3 5 7
Sample Output
2 3 5
题解:
迭代乱搜 跑得比dp还快..
1 #include <algorithm> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 using namespace std; 8 const int N=105; 9 int c,n,a[N];bool flag=0;int t[N],top=0,w[N],num=0; 10 bool check() 11 { 12 for(int i=1,j=1;i<=top && j<=num;i++,j++) 13 if(w[i]<t[i])return false; 14 else if(w[i]>t[i])return true; 15 if(top<num) 16 return true;return false; 17 } 18 void updata() 19 { 20 if(!num) 21 {for(int i=1;i<=top;i++)w[i]=t[i];num=top;} 22 else if(check()) 23 {for(int i=1;i<=top;i++)w[i]=t[i];num=top;} 24 else 25 return ; 26 } 27 void dfs(int tot,int dep,int lim,int last) 28 { 29 if(!tot) 30 { 31 flag=1; 32 updata(); 33 return ; 34 } 35 if(dep==lim+1)return ; 36 int k; 37 for(int i=last+1;i<=n;i++) 38 { 39 if(a[i]>tot)break;//重要！！！ 40 k=1; 41 while(k*a[i]<=tot) 42 { 43 t[++top]=a[i]; 44 dfs(tot-k*a[i],dep+1,lim,i); 45 top--; 46 k++; 47 } 48 } 49 } 50 int main() 51 { 52 scanf("%d%d",&c,&n); 53 for(int i=1;i<=n;i++){ 54 scanf("%d",&a[i]); 55 if(a[i]==1){ 56 printf("1 1 "); 57 return 0; 58 } 59 } 60 sort(a+1,a+n+1); 61 int ans; 62 for(ans=1;ans<=n;ans++) 63 { 64 dfs(c,1,ans,0); 65 if(flag)break; 66 } 67 printf("%d ",ans); 68 for(int i=1;i<=num;i++)printf("%d ",w[i]); 69 return 0; 70 }