当前位置: 首页 > 工具软件 > bcoin > 使用案例 >

算法——Coin Changing(最少硬币数)

穆毅然
2023-12-01

 题目描述

设有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(币值最大化问题)

 如果对你有帮助,记得点赞哟!

 类似资料: