최소 코인 수를 찾는 탐욕 알고리즘용 C/C++ 프로그램

그리디 알고리즘은 주어진 문제에 대한 최적의 솔루션을 찾는 데 사용되는 알고리즘입니다. 그리디 알고리즘은 각 부분에 대한 로컬 최적 솔루션(문제의 한 부분에 대한 최적 솔루션)을 찾는 방식으로 작동하므로 전역 최적 솔루션을 찾을 수 있음을 보여줍니다.

이 문제에서는 Greedy Algorithm 알고리즘을 사용하여 주어진 금액을 구성할 수 있는 최소 동전/노트 수를 찾습니다. 이를 위해 유효한 모든 동전이나 지폐, 즉 {1, 2, 5, 10, 20, 50, 100, 200, 500, 2000} 단위를 고려합니다. 합계를 구성하는 데 필요한 동전/노트의 수를 반환해야 합니다.

문맥을 더 잘 이해하기 위해 몇 가지 예를 들어 보겠습니다. -

예 1 -

Input : 1231
Output : 7

설명 - 500루피 지폐 2개, 100루피 지폐 2개, 20루피 지폐 1개, 10루피 지폐 1개와 루피 지폐 1장이 필요합니다. 다시 1코인. 총합은 2+2+1+1+1 = 7

예 2 -

Input : 2150
Output : 3

지침 - 2000루피 지폐 1개, 100루피 지폐 1개, 50루피 지폐 1개가 필요합니다.

그리디 알고리즘을 사용해 이 문제를 해결하기 위해 사용할 수 있는 최대 액면가의 지폐를 찾아보겠습니다. 그런 다음 합계에서 최대 액면가를 빼고 합계가 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

위 내용은 최소 코인 수를 찾는 탐욕 알고리즘용 C/C++ 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!