hdu 2126 Buy the souvenirs（求方案数的背包）

把排序的位置放错了，一直WA，不太细心

f[i][j]含义： i 元可以买 j 种物品的方案数，方案数f[i]=f[i]+f[i-a[i]]，很容易得到 f[i][j]=f[i][j]+f[i-a[i][j];

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 int cmp(const void *a,const void *b)
 5 {
 6     return *(int *)a-*(int *)b;
 7 }
 8 int main()
 9 {
10     int t,n,m,i,j,k;
11     int a[35],f[505][35];
12     scanf("%d",&t);
13     while(t--)
14     {
15         int tt;
16         scanf("%d%d",&n,&m);
17         int sum=0;
18         tt=0;
19         for(i=1;i<=n;i++)
20         {
21             scanf("%d",&a[i]);
22             
23         }
24         qsort(a+1,n,sizeof(a[0]),cmp);
25         for(i=1;i<=n;i++)
26         {
27         sum+=a[i];
28             if(sum<=m)
29                 tt=i;
30         }
31         if(sum<=m)
32         {
33             printf("You have 1 selection(s) to buy with %d kind(s) of souvenirs.
",n);
34             continue;
35         }
36         if(a[1]>m)
37         {
38             printf("Sorry, you can't buy anything.
");
39             continue;
40         }
41         memset(f,0,sizeof(f));
42       for(i=0;i<=m;i++)
43           f[i][0]=1;
44         for(i=1;i<=n;i++)
45         {
46             for(j=m;j>=a[i];j--)
47             {    
48              for(k=tt;k>=1;k--)
49                     f[j][k]=f[j][k]+f[j-a[i]][k-1];
50             }
51         }
52         if(f[m][tt]==0)
53             printf("Sorry, you can't buy anything.
");
54           else
55             printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.
",f[m][tt],tt);
56     
57     }
58     return 0;
59 }

View Code