HDU 2126 Buy the souvenirs (01背包,输出方案数)
题意:给出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; }