最小硬币找零问题

列出了硬币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