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...
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\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;
}
文章来源: xindoo.blog.csdn.net,作者:xindoo,版权归原作者所有,如需转载,请联系作者。
原文链接:xindoo.blog.csdn.net/article/details/8836122
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)