今天上午給學弟講背包的時候，看到背包裡面有一段關於求方案數的背包的論述。那會兒我自己也不太明白所以就沒講，結果下午就做了一道這樣的題目。
有n件物品，旅客一共有m塊大洋。第一個問題，旅客最多可以買多少件物品？請注意，這裡是多少件，不是價值最大。所以這個非常好求，將所有的物品按照價值排序，先買便宜的，再買貴的。貪心的思想。這個地方有些細節需要處理，如果所有物品的價值總和比旅客的錢少，那麼就只有一個方案，旅客可以買走所有的物品。如果旅客的錢數連第一件物品都買不起，那麼就直接輸出”Sorry，you
can't buy anything.“。
用這種方法，我們可以求出旅客最多買多少件物品，求出之後，物品的價格就有了兩種屬性，一種是錢數，一種是件數。也就是買一件物品需要的消耗是它的價格的錢數和1件物品的份額。在背包九講中，這個叫做二維費用的背包問題。
如果是求最優方案，這個問題依舊毫無壓力。但是現在的問題是求方案總數。
我們用dp[j][k]表示花費j元買k件物品的方案數，實際上很容易我們就可以得到dp[j][k]=dp[j][k]+dp[j-a[i]][k-1]。關於這個方程有兩個需要特別解釋的地方，第一個這個是空間優化後的方程，優化後的原理參見背包九講第一講01背包，這裡不再敘述。我們需要知道的是dp[j][k]在這裡指的是dp[i-1][j][k]，也就是在考慮過第i-1件物品後dp[j][k]的方案數。這個解釋了這個dp[j][k]為什麼可以直接繼承過來。第二個需要解釋的是，在dp[j][k]和dp[j-a[i]][k-1]中有沒有相同的方案，即我們有沒有冒著重復計算的風險將兩者相加。答案是沒有。因為在dp[j-a[i]][k-1]這些方案中都有第i件物品，我們說過dp[j][k]實際上是dp[i-1][j][k]，其中根本沒有第i件物品的影子，所以兩者不可能有重復的方案。
實際上如果了解第k大背包的算法的話，會對解決這道題有很大幫助。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 505
int dp[N][35];
int a[N];
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
int Max(int x,int y)
{
if(x>y)
return x;
else
return y;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
int sum;
sum=0;
int flag;
int i,j,k;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
qsort(a+1,n,sizeof(a[0]),cmp);
flag=0;
for(i=1;i<=n;i++)
{
sum+=a[i];
if(sum<=m)
flag=i;
}
if(sum<=m)
{
printf("You have 1 selection(s) to buy with %d kind(s) of souvenirs.\n",n);
continue;
}
else if(a[1]>m)
{
printf("Sorry, you can't buy anything.\n");
continue;
}
memset(dp,0,sizeof(dp));
for(i=0;i<=m;i++)
dp[i][0]=1;
for(i=1;i<=n;i++)
{
for(j=m;j>=a[i];j--)
{
for(k=flag;k>=1;k--)
dp[j][k]=dp[j][k]+dp[j-a[i]][k-1];
}
}
if(dp[m][flag]==0)
printf("Sorry, you can't buy anything.\n");
else
printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",dp[m][flag],flag);
}
return 0;
}
