最少硬币问题-蒲公英云

最少硬币问题

我就是我 2022-02-16 01:57 344阅读 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

Sample Output

5
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
int min(int a, int b) {
    return a < b ? a : b;
}
int main() {
    int n;
    int summoney;
    cin >> n;
    vector<int> t;
    vector<int> coin;
    int t1, coin1;//t 面值  coin  个数
    //方便起见  不用第0个元素存数据
    t.push_back(0);
    coin.push_back(0);
    for (int i = 1; i <= n; i++) {
        cin >> t1 >> coin1;
        t.push_back(t1);
        coin.push_back(coin1);
    }
    cin >> summoney;
    int dp[20005] = { 0 }; //dp[i] 用来记录钱数为i时的最少的硬币数
    for (int i = 1; i <= summoney; i++) {
        dp[i] = 99999;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= coin[i]; j++) {//此处就表示如果再用一个面值为t[i]的硬币还能不能找零
            for (int k = summoney; k >= t[i]; k--) {
                dp[k] = min(dp[k - t[i]]+1, dp[k]);
                //cout << k << ": " << dp[k] << endl; 
            }
        }
    }
    if (dp[summoney] == 99999) {
        cout << "-1" << endl;
    }
    else {
        cout << dp[summoney] << endl;
    }
    return 0;
}