http://acm.zjut.edu.cn/
不完全装满取值初始值都为0，恰好装满f[0]初始值为0，其他的为负无穷。
得到的玩具的价格按从大到小排序，保证当玩具组合出的价格等于擎天柱价格时，玩具的数量会是最少的
View Code
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 int f[10010]; 6 int c[10010]; 7 int main() 8 { 9 int n,m; 10 int p[20]; 11 while(~scanf("%d",&n)) //读数 12 { 13 for(int i= 0 ; i<n; i++) 14 { 15 scanf("%d",&p[i]); 16 } 17 scanf("%d",&m); 18 memset(c,0,sizeof(c)); 19 for(int i=1; i<=m; i++)//赋初值 20 f[i] = -10000; 21 f[0] = 0; 22 sort(p,p+n);//排序，保证放的玩具最少 23 for(int i= n-1; f[m] != m &&i>=0; i--) 24 { 25 for(int j=m; j>0; j--) 26 { 27 if(p[i] > j) continue; 28 int t = f[j-p[i]] + p[i]; 29 if(t>0) //能放满 30 { 31 f[j] = j; 32 c[j]= c[j-p[i]] +1; 33 if(j == m) break; 34 } 35 } 36 } 37 if(f[m] > 0) 38 printf("%d\n",c[m]); 39 else 40 printf("-1\n"); 41 } 42 return 0; 43 }