产生给定值的最小硬币数量
列出了硬币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)<<" 需要硬币。";
return 0;
}输出结果
Enter Value: 48 Minimum 7 需要硬币。