Minimum Number of Coins for Given Value (Coin Change Problem)

กำหนดเหรียญชุดหนึ่ง C = {c₁, c₂, ..., cₙ} (มีจำนวนไม่จำกัดแต่ละชนิด) และค่าเงิน V ต้องการหา จำนวนเหรียญน้อยที่สุด ที่รวมเป็น V

ตัวอย่าง Input และ Output

Coins: {1, 2, 5, 10}
Input: V = 48
Output: Minimum 7 coins required.
48 = 10 + 10 + 10 + 10 + 5 + 2 + 1

อัลกอริทึม Dynamic Programming (Unbounded Knapsack)

ฟังก์ชัน minCoins(coinList, n, value)

กำหนด:

coins[i] = จำนวนเหรียญน้อยที่สุดเพื่อทำค่า i

Recurrence:

coins[i] = min(coins[i], 1 + coins[i - coinList[j]]) สำหรับทุก j ที่ coinList[j] <= i

ขั้นตอน:

1. coins[0] = 0 (ค่า 0 ไม่ต้องเหรียญ)
2. for i = 1 ถึง value: coins[i] = INF
3. for i = 1 ถึง value:
   • for j = 0 ถึง n-1:
     • ถ้า coinList[j] <= i:
       • tempCoins = coins[i - coinList[j]]
       • ถ้า tempCoins != INF และ tempCoins + 1 < coins[i]:
       • coins[i] = tempCoins + 1
4. คืน coins[value]

ตัวอย่างโค้ด C++

#include <iostream>
#include <climits>
#include <algorithm>
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 << "Enter Value: "; cin >> value;
    cout << "Minimum " << minCoins(coins, n, value) << " coins required.";
    return 0;
}

Output

Enter Value: 48
Minimum 7 coins required.

ความซับซ้อน

• Time: O(n × value)
• Space: O(value)

หมายเหตุสำคัญ

• เป็น Unbounded Knapsack (เหรียญแต่ละชนิดมีไม่จำกัด)
• Greedy (เลือกเหรียญใหญ่สุดก่อน) **ไม่ได้** ทุกกรณี (เช่น coins={1,3,4}, V=6: Greedy ให้ 4+1+1=3 coins แต่ optimal คือ 3+3=2 coins)
• DP ให้คำตอบที่ถูกต้องเสมอ

การขยาย: นับจำนวนวิธี (Coin Change 2)

เปลี่ยน min เป็น + และ coins[0]=1 → ได้จำนวนวิธีการทำเงิน