数据结构
网络
RDBMS
操作系统
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 枚硬币，作为最少数量。
此算法的时间复杂度为 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
更新于: 15-6-2020
1K+ 浏览量
ADVERTISEMENT