xindoo is
always here

# light oj 1231-1232 – 1233- Coin Change 背包

In a strange shop there are n types of coins of value A1, A2 … AnC1, 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\n", tc, dp[k]);
}
return 0;
}

#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\n", tc, dp[k]);
}
return 0;
}

#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\n", ca, ans);
}
return 0;
}

• QQ咨询
• 回顶