首页 > 代码库 > hdu2126（求方案数的01背包）
hdu2126（求方案数的01背包）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2126
题意： n个物品，m元钱，每个物品最多买一次，问最多可以买几件物品，并且输出方案数。
分析：一看就想到01背包，不过得加一维来表示能买的物品件数。dp[i][j]表示在i元内至多能买j件物品。则状态转移方程为：dp[i][j]+=dp[i-a[k][j-1].
最后把在1~m元内买到的最大件数mx加起来就是题目所求。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 1000010#define clr(a) (memset(a,0,sizeof(a)))using namespace std;int dp[510][50],a[50];int n,m;int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); clr(dp); dp[0][0]=1; int mx=0; for(int i=1;i<=n;i++) for(int j=m;j>=a[i];j--) { for(int k=n-1;k>=0;k--) { if(dp[j-a[i]][k])dp[j][k+1]+=dp[j-a[i]][k],mx=max(mx,k+1); } } if(mx==0) { puts("Sorry, you can‘t buy anything."); continue; } int ans=0; for(int i=0;i<=m;i++)ans+=dp[i][mx]; printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",ans,mx); }}
hdu2126（求方案数的01背包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。