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

如果说把第一题看做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\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;
}


目录
相关文章
|
4月前
|
算法 测试技术
Big Event in HDU(dp算法)
Big Event in HDU(dp算法)
|
11月前
|
算法
light oj 1047 - Neighbor House 动态规划
动态规划,这个和刘汝佳算法竞赛入门经典P158的数字三角形有些相似,不过是求最小的值,而且有些限制,每次走到点和上次走的点不在同一列。
26 0
|
11月前
light oj 1159 - Batman LCS
学过简单动态规划的人应该对最长公共子序列的问题很熟悉了,这道题只不过多加了一条字符串变成三条了,还记得,只要把状态变成三维的即可。
30 0
LeetCode 322. Coin Change
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。
79 0
LeetCode 322. Coin Change
HDOJ 1391 Number Steps(打表DP)
HDOJ 1391 Number Steps(打表DP)
120 0
HDOJ 1391 Number Steps(打表DP)
Optimal Coin Change(完全背包计数)
题目描述 In a 10-dollar shop, everything is worthy 10 dollars or less. In order to serve customers more effectively at the cashier, change needs to be provided in the minimum number of coins. In this problem, you are going to provide a given value of the change in different coins.
86 0
|
Java Python
Leetcode-Medium 322. Coin Change
Leetcode-Medium 322. Coin Change
98 0
[转]POJ3624 Charm Bracelet(典型01背包问题)
来源:https://www.cnblogs.com/jinglecjy/p/5674796.html 题目链接:http://bailian.openjudge.cn/practice/4131/ Time Limit: 1000MS          Memory Limit: 65536K  ...
1232 0