首页 > 代码库 > HDU 2844 Coins(多重背包)
HDU 2844 Coins(多重背包)
HDU 2844 Coins(多重背包)
http://acm.hdu.edu.cn/showproblem.php?pid=2844
题意:
现在有价值val[1],val[2],…val[n]的n种硬币, 它们的数量分别为num[i]个. 然后给你一个m, 问你区间[1,m]内的所有数目, 由之前n种硬币来构造(即选取某些硬币使得这些硬币的价值和等于[1,m]区间的特定数), 最多能构造出这m个数中的多少个?
分析:
基本的完全背包问题.
我们令dp[i][j]==x表示用前i种硬币且硬币总价值总价值正好等于j时, 有多少种方法.
初始化: dp为全0,且 dp[0][0]==1.
对于每种硬币, 我们有两种可能的方式处理:
1. Val[i]*num[i]>= m时, 对当前硬币做一次完全背包即可.
2. Val[i]*num[i]<m时, 我们把当前硬币分成下面k+1类:
1个 2个 4个… 2^(k-1)个, 以及 num[i]-2^k+1个
然后我们对上面k+1类物品每个都做一次01背包即可, 因为对上面k+1类新物品的01选择会覆盖我们所有可能的对原来第i类物品做的任何选择.
最终所求: 所有使得dp[n][j]!=0 的j值得和. (1<=j<=m)
AC代码:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=100000+5; int n;//物品种数 int m;//总金钱数 int cost[100+5];//第i种物品的花费 int num[100+5]; //第i种物品的数量 int dp[maxn]; //1次01背包过程 void ZERO_ONE_PACK(int cost) { for(int i=m;i>=cost;i--) dp[i] += dp[i-cost]; } //1次完全背包过程 void COMPLETE_PACK(int cost) { for(int i=cost;i<=m;i++) dp[i] += dp[i-cost]; } //1次多重背包过程 void MULTIPLY_PACK(int cost,int num) { if(cost*num>=m) { COMPLETE_PACK(cost); return ; } int k=1; while(k<num) { ZERO_ONE_PACK(cost*k); num -= k; k*=2; } ZERO_ONE_PACK(cost*num); } int main() { while(scanf("%d%d",&n,&m)==2 && n) { //读取输入+初始化 for(int i=1;i<=n;i++) scanf("%d",&cost[i]); for(int i=1;i<=n;i++) scanf("%d",&num[i]); memset(dp,0,sizeof(dp)); dp[0]=1; //递推 for(int i=1;i<=n;i++) MULTIPLY_PACK(cost[i],num[i]); //统计结果ans int ans=0; for(int i=1;i<=m;i++)if(dp[i]) ans++; printf("%d\n",ans); } return 0; }
HDU 2844 Coins(多重背包)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。