数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究给定值的最少硬币数
给定一个硬币列表 C(c1, c2, ……Cn) 和一个值 V。现在问题是如何使用最少的硬币来凑成值 V。
注意：假设有无限数量的硬币 C。
在这个问题中，我们将考虑一组不同的硬币 C{1, 2, 5, 10}，每种类型的硬币都有无限个。为了凑成请求的值，我们将尝试取任意类型的最少硬币数量。例如，对于值 22：我们将选择 {10, 10, 2}，3 枚硬币是最少的。
输入和输出
Input: The required value. Say 48 Output: Minimum required coins. Here the output is 7. 48 = 10 + 10 + 10 + 10 + 5 + 2 + 1
算法
minCoins(coinList, n, value)
输入：不同的硬币列表、硬币数量、给定值。
输出：获得给定值的最小硬币数量。
Begin if value = 0, then return 0 define coins array of size value + 1, fill with ∞ coins[0] := 0 for i := 1 to value, do for j := 0 to n, do if coinList[j] <= i, then tempCoins := coins[i-coinList[j]] if tempCoins ≠ ∞ and (tempCoins + 1) < coins[i], then coins[i] := tempCoins + 1 done done return coins[value] End
示例
#include<iostream>
using namespace std;
int minCoins(int coinList[], int n, int value) {
int coins[value+1]; //store minimum coins for value i
if(value == 0)
return 0; //for value 0, it needs 0 coin
coins[0] = 0;
for (int i=1; i<=value; i++)
coins[i] = INT_MAX; //initially all values are infinity except 0 value
for (int i=1; i<=value; i++) { //for all values 1 to value, find minimum values
for (int j=0; j<n; j++)
if (coinList[j] <= i) {
int tempCoins = coins[i-coinList[j]];
if (tempCoins != INT_MAX && tempCoins + 1 < coins[i])
coins[i] = tempCoins + 1;
}
}
return coins[value]; //number of coins for value
}
int main() {
int coins[] = {1, 2, 5, 10};
int n = 4, value;
cout << "Enter Value: "; cin >> value;
cout << "Minimum "<<minCoins(coins, n, value)<<" coins required.";
return 0;
}输出
Enter Value: 48 Minimum 7 coins required.
更新于： 2020年6月17日
2K+ 浏览量
广告