poj 1742 Coins (多重背包)

题意很简单， 有n种硬币，每种硬币面额多大，有多少个，求可以构成m以内的面额有多少种。

开始用的是普通的多重背包的求法，裸裸的超时了，看了别人的代码，发现可以优化很多。

用usea这个来存储用来多少个a硬币，避免的很多无用的计算。

先贴以前超时的代码

#include <stdio.h>
#include <string.h>

int dp[100005];
int coin[101];
int cnt[101];
int used[1000101];

int main()
{
    int n, k;
    while(scanf("%d %d", &n, &k))
    {
        if (n==0 && k==0)
            break;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &coin[i]);
        }
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &cnt[j]);
        }
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            memset(used, 0, sizeof(used));
            for (int j = coin[i]; j <= k; j++)
            {
                if (!dp[j] && dp[j-coin[i]] && used[j-coin[i]] < cnt[i])
                {
                    ans++;
                    used[j]=used[j-coin[i]]+1;
                    dp[j] = 1;
                }
            }
        }
        printf("%d
", ans);
    }
    return 0;
}

下面是A了的代码

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

int a[105];
int c[105];
bool canpay[100005];
int usea[100005];
int main()
{
    int n, m;
    while (scanf("%d %d", &n, &m) && (m||n))
    {
        memset(canpay, 0, sizeof(canpay));
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++)
            scanf("%d", &c[i]);
        int ans = 0;
        canpay[0] = true;
        for (int i = 1; i <= n; i++)
        {
            memset(usea, 0, sizeof(usea));
            for (int j = a[i]; j <= m; j++)
            {
                if (!canpay[j] && canpay[j-a[i]] && usea[j - a[i]] < c[i])
                {
                    ans += 1;
                    canpay[j] = true;
                    usea[j] = usea[j - a[i]] + 1;
                }
            }
        }
        printf("%d
", ans);
    }
    return 0;
}