首页 > 代码库 > hdu2844（多重背包）
hdu2844（多重背包）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2844
题意：一位同学想要买手表，他有n种硬币，每种硬币已知有num[i]个。已知手表的价钱最多m元，问她用这些钱能够凑出多少种价格来买手表。
分析：二进制优化的多重背包，假设每种硬币为容量为val[i]且价值也为val[i]的物品，最后有dp[i]==i则能组成价格为i。因为容量为i能达到的最大价值也是i，刚好符合01背包的含义。
#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 100010using namespace std;int dp[N],val[110],num[110],a[N];int n,m,tot;int solve(){ for(int i=0;i<=m;i++)dp[i]=0; for(int i=1;i<tot;i++) { for(int j=m;j>=a[i];j--) dp[j]=max(dp[j],dp[j-a[i]]+a[i]); } int sum=0; for(int i=1;i<=m;i++)if(dp[i]==i)sum++; return sum;}int main(){ while(scanf("%d%d",&n,&m)&&(n+m)) { for(int i=1;i<=n;i++)scanf("%d",&val[i]); for(int i=1;i<=n;i++)scanf("%d",&num[i]); tot=1; for(int i=1;i<=n;i++) { for(int j=1;j<=num[i];j*=2) { a[tot++]=val[i]*j; num[i]-=j; } if(num[i])a[tot++]=num[i]*val[i]; } int ans=solve(); printf("%d\n",ans); }}
这题由于数据量较大，就算是二进制优化的多重背包也是998ms险过。这里可以增加一个一维数组use[ i ],记录到达i元时第j种钱用的次数。
#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 100010using namespace std;int dp[N],val[110],num[110],used[N];//i元钱时某种钱用的次数int n,m;int solve(){ int sum=0; for(int i=0;i<=m;i++)dp[i]=0; dp[0]=1; for(int i=1;i<=n;i++) { memset(used,0,sizeof(used));//每次初始化第i种钱用了0次 for(int j=val[i];j<=m;j++) { if(!dp[j]&&dp[j-val[i]]&&used[j-val[i]]<num[i])//到达j元用的i种钱的次数是到达 j-val[i]元用的次数加1 { dp[j]=1;used[j]=used[j-val[i]]+1;sum++; } } } return sum;}int main(){ while(scanf("%d%d",&n,&m)&&(n+m)) { for(int i=1;i<=n;i++)scanf("%d",&val[i]); for(int i=1;i<=n;i++)scanf("%d",&num[i]); int ans=solve(); printf("%d\n",ans); }}
hdu2844（多重背包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。