1725 最少硬币问题

傷城~ 2022-02-15 06:24 236阅读 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>
    using namespace std;
    #define inf 0x3f3f3f3f
    
    int main() {
      int T[20],corn[20],dp[20020];
      int n,m;
      std::cin >> n;
      for(int i = 0; i < n; i++)
        std::cin >> T[i] >> corn[i];
      std::cin >> m;
      for(int i = 1; i <= m; i++)
        dp[i] = inf;
      for(int i = 0; i < n; i++)
        for(int j =1; j <= corn[i]; j++)
          for(int k = m; k >= T[i]; k--)
            dp[k] = min(dp[k],dp[k-T[i]]+1);
      std::cout << (dp[m]<m?dp[m]:-1) << '\n';
      return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关硬币问题

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

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

相关凑硬币问题

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

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

相关最少硬币问题

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

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

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

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

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

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

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

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

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

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

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

相关最少硬币问题

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

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

相关最少硬币问题

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

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

相关 1725 最少硬币问题

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

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

相关最少转弯问题

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

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