题意：
         输入的第一行为一个正整数N（1<=N<=40)。下面有N行输入数据，每一行第一个数t为找零的总数，后面6个数字m1，m2, m3, m4, m5, m6分别为现有面值为50,20,10,5,2,1纸币的张数。 如果能够找出总数为t的零钱，那么输出最少的张数的方案。如 s1 s2 s3 s4 s5.分别表示为找零面值为50 20 10 5 2 1的张数。si si+1之间用空格
隔开s5后面没有空格。否则输出Refuse。每个输出占一行。

分析：显然背包的容量为 T ，即选择满足容量的最小解。首先对于设 F[i] 表示在背包容量为 i  的情况下的最优解是 cnt[i][0--5]。则F[i]=max(F[i],F[i-w[j]]+w[j]); 如果 F[i]不变，则跟新cnt[i][0--5];  

 1#include<iostream>
 2using namespace std;
 3const int maxn=100000;
 4 
 5int s[6];
 6int val[6]={50,20,10,5,2,1};
 7int v,cnt[maxn][6];
 8int f[maxn];
 9
10int main()
11{
12    int  i,j,k,t,t1,t2;
13    scanf("%d",&t);
14    while(t--)
15    {   
16            scanf("%d",&v);
17        for(i=0;i<6;i++)
18            scanf("%d",&s[i]);
19
20        memset(f,0,sizeof(f));
21        memset(cnt,0,sizeof(cnt));
22
23        for(i=0;i<=v;i++)
24        {   
25            for(j=0;j<6;j++)
26            {   
27                if(i<val[j])continue;
28
29                if(cnt[i-val[j]][j]+1<=s[j])
30                {
31                   if(f[i]<f[i-val[j]]+val[j])
32                   {
33                      f[i]=f[i-val[j]]+val[j];
34
35                          for(k=0;k<6;k++)
36                            cnt[i][k]=cnt[i-val[j]][k];
37                        cnt[i][j]++;
38                   }
39                   else if(f[i]==f[i-val[j]]+val[j])
40                   {   
41                        t1=0;t2=1;
42                        for(k=0;k<6;k++)
43                        {
44                            t1+=cnt[i][k];
45                            t2+=cnt[i-val[j]][k];
46                        }
47                        if(t2<t1)
48                        {  
49                            for(k=0;k<6;k++)
50                            cnt[i][k]=cnt[i-val[j]][k];
51                            cnt[i][j]++;
52                        }
53                   }
54                }
55            }
56        }
57        if(f[v]!=v)
58        {
59            printf("Refuse\n");
60        }
61        else 
62        {
63            for(i=0;i<5;i++)
64                printf("%d ",cnt[v][i]);
65            printf("%d\n",cnt[v][5]);
66        }
67    }
68    return 0;
69}