【POJ 1742】Coins【DP】【多重背包】

本文主要是介绍【POJ 1742】Coins【DP】【多重背包】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

题目链接：http://poj.org/problem?id=1742
有$n$种面值不同的硬币，每种有$c[i]$个。求1到$m$有多少面值可以用这些硬币凑成？

---

思路：

很明显的完全背包。。。



前面$WA,TLE,RE,CE$全是用二进制拆分做的。。。后来实在没办法打了书上的方法。
设$f[i]$为面值为$i$可否得到。那么最基本的$O(tn{m}^2)$肯定是过不了的。需要优化。
设$used[i]$表示面值凑到$i$的最小硬币使用数，那么我们就可以省掉一重循环，因为，可以用$used$来进行最小答案的判断。
最终答案为${\sum }_{i=1}^{n}f[i]$
时间复杂度：$O(tnm)$

---

代码：

#include <cstdio>
#include <cstring>
using namespace std;int n,m,c[101],a[101],used[100001],sum;
bool f[100001];int main()
{while (scanf("%d%d",&n,&m)==2){if (!n&&!m) return 0;memset(f,0,sizeof(f));memset(c,0,sizeof(c));memset(a,0,sizeof(a));f[0]=true;  //初始化for (int i=1;i<=n;i++) scanf("%d",&a[i]);for (int i=1;i<=n;i++) scanf("%d",&c[i]);for (int i=1;i<=n;i++){memset(used,0,sizeof(used));  //对于不同的i都要清空。for (int j=a[i];j<=m;j++)if (used[j-a[i]]<c[i]&&!f[j]&&f[j-a[i]])  {used[j]=used[j-a[i]]+1;  //要多使用一枚硬币f[j]=true;}}sum=0;for (int i=1;i<=m;i++)sum+=f[i];printf("%d\n",sum);}
}

这篇关于【POJ 1742】Coins【DP】【多重背包】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---