首页 > 代码库 > 硬币问题 （dp，多重背包的二分优化）
硬币问题 （dp，多重背包的二分优化）
题目描述
给你n种硬币，知道每种的面值Ai和每种的数量Ci。问能凑出多少种不大于m的面值。
输入
有多组数据，每一组第一行有两个整数 n(1≤n≤100)和m(m≤100000)，第二行有2n个整数，即面值A1，A2，A3，…，An和数量C1，C2，C3，…，Cn (1≤Ai≤100000，1≤Ci≤1000)。所有数据结束以2个0表示。
输出
每组数据输出一行答案。
样例输入
3 101 2 4 2 1 12 51 4 2 10 0样例输出
84
背包问题的复杂度是n*m，这题如果直接按照多重背包的计算会超时。所以和上一篇一样，多重背包的二分优化。
详细的说明在 http://www.cnblogs.com/agenthtb/p/5792628.html
代码如下：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int w[100010],v[20010],maxn=0,dp[100010],n,m,cnt,x; 6 void f(int weight,int num)//把硬币进行二分的合并 7 { 8 for (int i=1;;i*=2) 9 {10 if (num>=i)11 w[cnt++]=weight*i;12 else13 {14 w[cnt++]=num*weight;15 return;16 }17 num-=i;18 if (num<=0)19 return;20 }21 }22 int main()23 {24 //freopen("de.txt","r",stdin);25 while (~scanf("%d%d",&n,&m))26 {27 if (n==0&&m==0)28 break;29 memset(w,0,sizeof w);30 memset(v,0,sizeof v);31 memset(dp,0,sizeof dp);32 dp[0]=1;33 set<int>s;34 cnt=1;35 for (int i=1;i<=n;++i)36 scanf("%d",&v[i]);37 for (int i=1;i<=n;++i)38 {39 scanf("%d",&x);40 f(v[i],x);41 }42 for (int i=1;i<cnt;++i)43 {44 for (int j=m;j>=w[i];--j)45 {46 if (dp[j-w[i]])47 dp[j]=1;48 }49 }50 int ans=0;51 for (int i=1;i<=m;++i)52 if (dp[i]) ans++;53 printf("%d\n",ans);54 }55 return 0;56 }
硬币问题 （dp，多重背包的二分优化）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。