Số lượng xu tối thiểu tạo ra một giá trị nhất định

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ô hạn 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} được cho, Có vô hạn số đồng tiền của mỗi loại. Để 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.

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

Input:
The required value. Say 48
Output:
Minimum required coins. Here the output is 7.
48 = 10 + 10 + 10 + 10 + 5 + 2 + 1

Thuật toán

minCoins(coinList, n, value)

Đầu vào: danh sách các loại tiền khác nhau, số lượng tiền, giá trị nhất định.

Đầu ra: Số lượng xu tối thiểu để nhận được giá trị nhất định.

Begin
   if value = 0, then
      return 0
   define coins array of size value + 1, fill with ∞
   coins[0] := 0

   for i := 1 to value, do
      for j := 0 to n, do
         if coinList[j] <= i, then
            tempCoins := coins[i-coinList[j]]
         if tempCoins ≠ ∞ and (tempCoins + 1) < coins[i], then
            coins[i] := tempCoins + 1
      done
   done

   return coins[value]
End

Ví dụ

#include<iostream>
using namespace std;

int minCoins(int coinList[], int n, int value) {
   int coins[value+1];       //store minimum coins for value i

   if(value == 0)
      return 0;              //for value 0, it needs 0 coin

   coins[0] = 0;

   for (int i=1; i<=value; i++)
      coins[i] = INT_MAX;            //initially all values are infinity except 0 value

   for (int i=1; i<=value; i++) {      //for all values 1 to value, find minimum values
      for (int j=0; j<n; j++)
         if (coinList[j] <= i) {
            int tempCoins = coins[i-coinList[j]];
         if (tempCoins != INT_MAX && tempCoins + 1 < coins[i])
            coins[i] = tempCoins + 1;
      }
   }
   return coins[value];       //number of coins for value
}

int main() {
   int coins[] = {1, 2, 5, 10};
   int n = 4, value;
   cout << "Enter Value: "; cin >> value;
   cout << "Minimum "<<minCoins(coins, n, value)<<" coins required.";
   return 0;
}

Đầu ra

Enter Value: 48
Minimum 7 coins required.