Số Đồng Xu Tối Thiểu Để Đổi Tiền (Minimum Coins Change)

Giới thiệu

Cho các mệnh giá đồng xu và một giá trị V. Tìm số đồng xu ít nhất để tổng bằng V (giả sử số lượng mỗi mệnh giá vô hạn).

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

Đầu vào: Mệnh giá {1, 2, 5, 10}, V = 48
Đầu ra: 7 đồng xu (10+10+10+10+5+2+1).

Thuật toán Quy hoạch động

Mảng coins[i] lưu số đồng xu ít nhất để tạo giá trị i. Khởi tạo coins[0]=0, các giá trị khác = ∞. Với mỗi i từ 1 đến V, thử mọi mệnh giá coinList[j] ≤ i, cập nhật coins[i] = min(coins[i], coins[i - coinList[j]] + 1).

minCoins(coinList, n, value)
Begin
    if value = 0 return 0
    định nghĩa coins[0..value], điền ∞, coins[0] := 0
    for i := 1 to value do
        for j := 0 to n-1 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
    done
    return coins[value]
End

Ví dụ C++

#include <iostream>
using namespace std;

int minCoins(int coinList[], int n, int value) {
    int coins[value+1];
    if (value == 0) return 0;
    coins[0] = 0;
    for (int i = 1; i <= value; i++) coins[i] = INT_MAX;
    for (int i = 1; i <= value; i++) {
        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];
}

int main() {
    int coins[] = {1, 2, 5, 10};
    int n = 4, value;
    cout << "Nhập giá trị: "; cin >> value;
    cout << "Tối thiểu " << minCoins(coins, n, value) << " đồng xu.";
    return 0;
}

Kết quả

Nhập giá trị: 48
Tối thiểu 7 đồng xu.