最少硬币问题

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

#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;
    }