算法——Coin Changing（最少硬币数）

 题目描述

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

输入

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

输出

最少硬币数,无解时输出-1

样例输入

3
1 3
2 3
5 3
18

样例输出

5

---

 

这道题是一道动态规划的题目，半天想不明白要怎么下手，于是乎按照自己的思路解题：

• 将数组从大到小排序，用快排；
• 然后在数组中，判断找零数 m 是否大于硬币的数值，其对应硬币是不是被用完了；
• 如果满足上面的条件，则该数值的硬币是找零的其中之一 ，m减该数值得到新的零钱数；
• 重复进行上面的操作，如果最后可以得到 m 等于 0，则输出最小硬币数，否则，输出-1.

先看看代码：

typedef struct {
	int T;
	int Coins;
}Mo;
bool cmp(Mo a, Mo b){
	return a.T > b.T ;
}
int ChangeMaking(int m, int n, Mo *a){
	sort(a,a+n,cmp); 
	int flag = 0;
	for(int i = 0; i < n; i++){
		while(a[i].Coins > 0 && m - a[i].T  >= 0){
			m -= a[i].T ;
			flag ++;
			a[i].Coins --;
		}
	}
	if(flag != 0 && m == 0) return flag;
	else return -1;
}

 你也觉得没有什么毛病，对吧？那就大错特错了。看这个例子：

设找零数 m = 8，有 1 个 5 ，2 个 4， 1 个 2。 这个例子看简单，看得出最小的硬币数是2个（2个4），但是按照上述的算法那么就会无解，与正确答案相矛盾。

所以，我们还是老老实实学习动态规划的算法，对此题作解。

下列是完整的代码。

代码

 

#include<iostream>
using namespace std;
int T[11],Coins[11];
int main(){
	int n,m;
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>T[i]>>Coins[i];
	}
	cin>>m;
	int dp[20001];
	for(int i = 1; i < 20001; i++){
		dp[i] = 101;
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= Coins[i] ; j++ ){
			for(int k = m; k >= T[i]; k --){
				dp[k]=min(dp[k-T[i]] + 1,dp[k]);
			}
		}
	}
	if(dp[m] == 101) cout<<"-1"<<endl;
	else cout<<dp[m]<<endl;
	return 0;
}

思路

• 用了动态规划的算法；
• 此题的详细思路会在后续版本给出。

推荐题目

1.  算法——Coin-collecting by robot（硬币收集问题）
2. 算法——Coin-row problem（币值最大化问题）

 如果对你有帮助，记得点赞哟！