資料結構
網路
關係資料庫管理系統
作業系統
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-06-17
2K+ 瀏覽量
廣告