light oj 1231-1232-1233-Coin Changeリュックサック

タイトルリンク
In a strange shop there are n types of coins of value A1, A2 ... An. C1, C2, ... Cn denote the number of coins of value A1, A2 ... An respectively. You have to find the number of ways you can make K using the coins.
For example, suppose there are three coins 1, 2, 5 and we can use coin 1 at most 3 times, coin 2 at most 2 times and coin 5 at most 1 time. Then if K = 5 the possible ways are:
1112
122
5  ………………………………
しばらくは分からないまで分からないので、人の子弟を間違えず、コードを貼ってしまいました.

#include <stdio.h>
#include <string.h>
const int mod = 100000007;
int dp[1005];
int coin[55];
int cnt[55];

int main()
{
    int t, n, k;
    scanf("%d", &t);
    for (int tc = 1; tc <= t; tc++)
    {
        scanf("%d %d", &n, &k);
        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;
        for (int i = 1; i <= n; i++)
        {
            for (int j = k; j >= 0; j--)
            {
                for (int l = 1; l <= cnt[i]; l++)
                {
                    if (j - l*coin[i] >= 0)
                    dp[j] += dp[j-coin[i]*l];
                }
            }
            for (int j = 0; j <= k; j++)
                dp[j] %= mod;
        }
        printf("Case %d: %d
", tc, dp[k]);
    }
    return 0;
}

第1題を01リュックとして考えると、この問題は完全リュックということになります

#include <stdio.h>
#include <string.h>
const int mod = 100000007;
int dp[10050];
int coin[105];

int main()
{
    int t, n, k;
    scanf("%d", &t);
    for (int tc = 1; tc <= t; tc++)
    {
        scanf("%d %d", &n, &k);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &coin[i]);
        }

        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            for (int j = coin[i]; j <= k; j++)
            {
                dp[j] += dp[j-coin[i]];
                dp[j] %= mod;
            }
        }
        printf("Case %d: %d
", tc, dp[k]);
    }
    return 0;
}

第3題はまた完全なリュックサックです

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

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

int main()
{
    int t, n, k;
    scanf("%d", &t);
    for (int ca = 1; ca <= t; ca++)
    {
        scanf("%d %d", &n, &k);
        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("Case %d: %d
", ca, ans);
    }
    return 0;
}