poj1742 281. 硬币（多重背包）

本文主要是介绍poj1742 281. 硬币（多重背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定N种硬币，其中第 i 种硬币的面值为Ai,共有Ci个。

从中选出若干个硬币，把面值相加，若结果为S，则称“面值S能被拼成”。

求1~M之间能被拼成的面值有多少个。

输入格式
输入包含多组测试用例。

每组测试用例第一行包含两个整数N和M。

第二行包含2N个整数，分别表示A1,A2,…,AN和C1,C2,…,CN。

当输入用例N=0，M=0时，表示输入终止，且该用例无需处理。

输出格式
每组用例输出一个结果，每个结果占一行。

数据范围
1≤N≤100,
1≤M≤105,
1≤Ai≤105,
1≤Ci≤1000
输入用例：
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0
输出用例：
8
4

思路： 多重背包。这里是当做01背包写。单调队列优化，二进制拆分还没写。

#include <cstdio>
#include <cstring>using namespace std;int a[105],b[105],c[100005],d[100005];int main()
{int n,m;while(~scanf("%d%d",&n,&m) && n && m){memset(d,0,sizeof(d));for(int i = 1;i <= n;i++)scanf("%d",&a[i]);for(int i = 1;i <= n;i++)scanf("%d",&b[i]);d[0] = 1;for(int i = 1;i <= n;i++){for(int j = 0;j <= m;j++)c[j] = 0;for(int j = a[i];j <= m;j++){if(c[j - a[i]] < b[i] && d[j - a[i]] == 1 && d[j] == 0){d[j] = 1;c[j] = c[j - a[i]] + 1;}}}int ans = 0;for(int i = 1;i <= m;i++){if(d[i])ans++;}printf("%d\n",ans);}return 0;
}

这篇关于poj1742 281. 硬币（多重背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---