탐욕 알고리즘은 주어진 문제에 대한 최적의 솔루션을 찾는 데 사용되는 알고리즘입니다. greedy 알고리즘은 각 부분의 로컬 최적 솔루션(문제의 일부에 대한 최적 솔루션)을 찾는 방식으로 작동하므로 글로벌 최적 솔루션을 찾을 수 있음을 보여줍니다.
이 문제에서는 greedy 알고리즘을 사용하여 주어진 합계를 구성할 수 있는 최소 동전/주화 수를 찾습니다. 이를 위해 {1, 2, 5, 10, 20, 50, 100, 200, 500,2000 }의 모든 유효한 동전이나 지폐를 고려할 것입니다. 그리고 총액을 채우는 데 필요한 코인/노트의 수를 반환해야 합니다.
문맥을 더 잘 이해하기 위해 몇 가지 예를 들어보겠습니다 -
예시 1 -
Input : 1231 Output : 7
설명 − 2개의 Rs 500 지폐, 2개의 Rs 100 지폐, 1개의 Rs 20 지폐, 1개의 Rs 10 지폐 및 1개의 Re 1 동전이 필요합니다. 합계는 2+2+1+1+1 =7
예시 2 -
Input : 2150 Output : 3
설명 − 2000루피 지폐 1장, 100루피 지폐 1장, 50루피 지폐 1장이 필요합니다.
greedy 알고리즘을 사용하여 이 문제를 해결하기 위해 사용할 수 있는 가장 큰 단위를 찾습니다. 그런 다음 합계에서 가장 큰 금액을 빼고 합계가 0이 될 때까지 동일한 과정을 다시 수행합니다.
알고리즘
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