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

题目大意：

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

---

思路：

很明显的完全背包。。。



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