資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C/C++ 貪心演算法求最小硬幣數量程式
貪心演算法是一種用於為給定問題找到最優解的演算法。貪心演算法的工作原理是找到每個部分的區域性最優解（問題一部分的最優解），從而顯示可以找到全域性最優解。
在這個問題中，我們將使用貪心演算法來找到可以構成給定總和的最小硬幣/鈔票數量。 為此，我們將考慮所有有效的硬幣或鈔票，即面額 { 1, 2, 5, 10, 20, 50 , 100, 200 , 500 ,2000 }。我們需要返回構成總和所需的這些硬幣/鈔票的數量。
讓我們舉幾個例子來更好地理解上下文 -
示例 1 -
Input : 1231 Output : 7
說明 - 我們將需要兩張 500 元的鈔票，兩張 100 元的鈔票，一張 20 元的鈔票，一張 10 元的鈔票和一枚 1 元的硬幣。總計為 2+2+1+1+1 = 7
示例 2 -
Input : 2150 Output : 3
說明 - 我們將需要一張 2000 元的鈔票，一張 100 元的鈔票和一張 50 元的鈔票。
為了使用貪心演算法解決此問題，我們將找到可以使用哪種最大的面額。然後，我們將從總和中減去最大的面額，並再次執行相同的過程，直到總和變為零。
演算法
Input: sum, Initialise the coins = 0 Step 1: Find the largest denomination that can be used i.e. smaller than sum. Step 2: Add denomination two coins and subtract it from the Sum Step 3: Repeat step 2 until the sum becomes 0. Step 4: Print each value in coins.
示例
#include <bits/stdc++.h>
using namespace std;
int notes[] = { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000 };
int n = sizeof(notes) / sizeof(notes[0]);
void minchange(int sum){
vector<int> coins;
for (int i = n - 1; i >= 0; i--) {
while (sum >= notes[i]) {
sum -= notes[i];
coins.push_back(notes[i]);
}
}
for (int i = 0; i < coins.size(); i++)
cout << coins[i] << "\t";
}
int main(){
int n = 3253;
cout << "The minimum number of coins/notes that sum up " << n << " is \t ";
minchange(n);
return 0;
}輸出
The minimum number of coins/notes that sum up 3253 is 2000 500 500 200 50 2 1
更新於: 2019-09-19
5K+ 瀏覽量
廣告