最少硬币问题

野性酷女 2022-02-17 12:14 206阅读 0赞

### 最少硬币问题 ###

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

设有n种不同面值的硬币，各硬币的面值存于数组T\[1:n\]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins\[1:n\]中。  
对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。  
对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0≤m≤20001，计算找钱m的最少硬币数。

Input

输入数据第一行中只有1个整数给出n的值,第2行起每行2个数，分别是T\[j\]和Coins\[j\]。最后1行是要找的钱数m。

Output

输出数据只有一个整数，表示计算出的最少硬币数。问题无解时输出-1。

Sample Input

3
    1 3
    2 3
    5 3
    18

Sample Output

5

#include <bits/stdc++.h>
    #define maxinum 20002
    
    using namespace std;
    
    int main()
    {
        int n, m;
        int i, j, k;
        int t[maxinum], coins[maxinum];
        int dp[maxinum];
        scanf("%d", &n);
        for(i = 1; i <= n; i++)
        {
            scanf("%d%d", &t[i], &coins[i]);
        }
        scanf("%d", &m);
        for(i = 1; i <= m; i++)
        {
            dp[i] = 99999;
        }
        for(i = 1; i <= n; i++)
        {
            for(j = 1; j <= coins[i]; j++)
            {
                for(k = m; k >= t[i]; k--)
                {
                    dp[k] = min(dp[k - t[i]] + 1, dp[k]);
                }
            }
        }
        if(dp[m] == 99999)
            printf("-1\n");
        else
            printf("%d\n", dp[m]);
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，206人围观）

还没有评论，来说两句吧...

相关阅读

相关硬币问题

include <bits/stdc++.h> using namespace std; const int maxn = 2e5+10;...

女爷i/ 2024年04月17日 17:52/ 0 赞/ 60 阅读

相关凑硬币问题

/ 给出k中面值的硬币，每种硬币的数量无限，再给一个总金额amount，问最少需要几枚硬币凑出这个金额，如果凑不出，返回-1 dp[i]定义：当目标金额为i时，至少

迷南。/ 2022年10月27日 13:54/ 0 赞/ 180 阅读

相关最少硬币问题

最少硬币问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Problem Descri

- 日理万妓/ 2022年05月27日 10:11/ 0 赞/ 206 阅读

相关最少硬币问题（多重背包）

Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Problem Description 设

傷城~/ 2022年05月27日 06:15/ 0 赞/ 186 阅读

相关【贪心策略】硬币问题

问题描述：有vi=1元、5元、10元、50元、100元、500元的硬币c1、c2、c3、c4、c5枚。若用这些硬币来凑出A元，最少需要多少枚硬币？贪心策略：初始化n

绝地灬酷狼/ 2022年04月02日 04:18/ 0 赞/ 265 阅读

相关 Python之动态规划（最少硬币数找零）

完整代码：动态规划最少硬币数找零 def dpMakeChange(coinValueList, change, minCoins, coinsUsed)

忘是亡心i/ 2022年02月19日 00:29/ 0 赞/ 434 阅读

相关最少硬币问题

最少硬币问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 设有n种不同面值的硬币，

野性酷女/ 2022年02月17日 12:14/ 0 赞/ 207 阅读

相关最少硬币问题

最少硬币问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 设有n种不同面值的硬币，

我就是我/ 2022年02月16日 01:57/ 0 赞/ 240 阅读

相关 1725 最少硬币问题

最少硬币问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 设有n种不同面值的硬币，

傷城~/ 2022年02月15日 06:24/ 0 赞/ 230 阅读

相关最少转弯问题

问题描述给出一张地图，这张地图被分为n×m（n,m<=100）个方块，任何一个方块不是平地就是高山。平地可以通过，高山则不能。现在你处在地图的（x1,y1）这块平地，问：你

朴灿烈づ我的快乐病毒、/ 2022年02月04日 14:57/ 0 赞/ 221 阅读