Vấn đề thay đổi số xu tối thiểu

Có một danh sách các đồng xu C (c1, c2, …… Cn) được đưa ra và một giá trị V cũng được đưa ra. Bây giờ vấn đề là sử dụng số xu tối thiểu để tạo ra cơ hội V.

Lưu ý - Giả sử có vô số đồng xu C

Trong bài toán này, chúng ta sẽ xem xét một tập hợp các đồng tiền khác nhau C {1, 2, 5, 10} đã cho, Mỗi loại có vô số đồng xu. Để thực hiện thay đổi giá trị được yêu cầu, chúng tôi sẽ cố gắng lấy số lượng tối thiểu của bất kỳ loại tiền nào.

Ví dụ:đối với giá trị 22 - chúng tôi sẽ chọn tối thiểu {10, 10, 2}, 3 xu.

Độ phức tạp thời gian của thuật toán này id O (V), trong đó V là giá trị.

Đầu vào và Đầu ra

Input:
A value, say 47
Output:
Enter value: 47
Coins are: 10, 10, 10, 10, 5, 2

Thuật toán

findMinCoin(value)

Đầu vào - Giá trị để thực hiện thay đổi

Đầu ra - Bộ tiền xu.

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

Ví dụ

#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;
}

Đầu ra

Enter value: 47
Coins are: 10, 10, 10, 10, 5, 2