列出了硬币C(c1,c2,…Cn),还给出了值V。现在的问题是使用最少的硬币数来获得机会V。
注意- 假设有无限数量的硬币C
在这个问题中,我们将考虑给定一组不同的硬币C {1、2、5、10},每种类型的硬币数量都是无限的。为了更改要求的值,我们将尝试采用最少数量的任何类型的硬币。
例如,对于值22-,我们将选择{10,10,2},3个硬币作为最小值。
此算法的时间复杂度为O(V),其中V为值。
Input: A value, say 47 Output: Enter value: 47 Coins are: 10, 10, 10, 10, 5, 2
findMinCoin(value)
输入- 进行更改的值
输出-硬币组。
Begin coins set with value {1, 2, 5, 10} for all coins i as higher value to lower value do while value >= coins[i] do value := value – coins[i] add coins[i], in thecoin list done done print all entries in the coin list. End
#include<iostream> #include<list> #define COINS 4 using namespace std; float coins[COINS] = {1, 2, 5, 10}; void findMinCoin(int cost) { list<int> coinList; for(int i = COINS-1; i>=0; i--) { while(cost >= coins[i]) { cost -= coins[i]; coinList.push_back(coins[i]); //add coin in the list } } list<int>::iterator it; for(it = coinList.begin(); it != coinList.end(); it++) { cout << *it << ", "; } } main() { int val; cout << "Enter value: "; cin >> val; cout << "Coins are: "; findMinCoin(val); cout << endl; }
输出结果
Enter value: 47 Coins are: 10, 10, 10, 10, 5, 2