题意：给出t组数据
每组数据给出n和m，n代表商品个数，m代表你所拥有的钱，然后给出n个商品的价值
问你所能买到的最大件数，和对应的方案数。
思路：
如果将物品的价格看做容量，将它的件数1看做价值的话，那么用01背包就可以求的花费m钱所能买到的最大件数dp[m]。
但是题目还要求方案数，因此很容易想到再建立一个数组f[j]，存储j元钱能买dp[j]个物品的方案数。
在求解01背包的过程中，要分两种情况讨论：
设当前所选的物品为i
1. 若选了物品i后，能买的件数比不选物品i的件数大，即dp[j-val[i]]>dp[j]
那么更新dp[j]，同时，f[j]的方案数即为f[j-val[i]]
原因是：假设f[j-val[i]]的方案数为 AB AC 两种，那么在此情况下加个D，为ABD,ACD，仍为两种，所以f[j]=f[j-val[i]]即可
当然，要注意f[j-val[i]]为0的情况，因此当它为0时，f[j]=1，1即为D
2. 若选了物品i后，能买的件数比不选物品i的件数相同，即dp[j-val[i]]==dp[j]
即原先不选第i个物品，所需要的方案数为f[j]；而选了物品i的方案数为f[j-val[i]]。
因此，总的方案数即为f[j]+f[j-val[i]]
当然，这里也要注意f[j-val[i]]=0的情况，当它为0时，f[j]+=1，1即为D
一开始，就是这里忘记判断了，导致WA。。。
时间0ms，内存260K，在HDU AC的136个人里面，排名第10，哈哈！
#include <iostream> #include <stdio.h> #include <algorithm> #include <cstring> using namespace std; const int maxn=31; const int maxm=501; int n,m; int val[maxn]; //存储物品的价格 int dp[maxm]; //dp[j]表示j元钱能买的最大物品件数 int f[maxm]; //f[j]表示j元钱能买dp[j]个物品的方案数 int main() { int t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); val[0]=0; for(int i=1;i<=n;i++) scanf("%d",&val[i]); memset(f,0,sizeof(f)); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){ for(int j=m;j>=val[i];j--){ if(dp[j-val[i]]+1>dp[j]){ dp[j]=dp[j-val[i]]+1; if(f[j-val[i]]) f[j]=f[j-val[i]]; //当f[j-val[i]]>0时，直接赋值即可 else f[j]=1; //当f[j-val[i]]=0时，应该算1种，即当前选择的第i件物品 } else if(dp[j-val[i]]+1==dp[j]){ if(f[j-val[i]]) f[j]+=f[j-val[i]]; //当f[j-val[i]]>0时，直接加上即可 else f[j]+=1; //当f[j-val[i]]=0时，应该算1种，即当前选择的第i件物品 } } } if(dp[m]==0){ printf("Sorry, you can't buy anything. "); } else{ printf("You have %d selection(s) to buy with %d kind(s) of souvenirs. ",f[m],dp[m]); } } return 0; }