최소 코인 변경 문제

C(c1, c2, …Cn) 코인 목록이 있으며 V 값도 제공됩니다. 이제 문제는 최소한의 코인을 사용하여 기회를 V로 만드는 것입니다.

참고 - 무한한 수의 동전이 있다고 가정합니다. C

이 문제에서는 서로 다른 동전 집합 C{1, 2, 5, 10}가 주어졌을 때 각 유형의 동전 수가 무한대라고 생각합니다. 요청된 값을 변경하기 위해 모든 유형의 최소 동전 수를 사용하려고 합니다.

예를 들어 값이 22인 경우 최소값으로 {10, 10, 2}, 3개의 동전을 선택합니다.

이 알고리즘의 시간 복잡도 id 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