หาจำนวนธนบัตรน้อยที่สุดสำหรับจำนวนเงินที่กำหนดใน C++ (Greedy)

หาจำนวนธนบัตรน้อยที่สุดรวมเป็นจำนวนเงินที่กำหนด ใช้ธนบัตร: {2000, 500, 200, 100, 50, 20, 10, 5, 2, 1} (สมมติมีไม่จำกัด)

ตัวอย่าง: 1072 → 500×2, 50×1, 20×1, 2×1 = 5 ใบ

อัลกอริทึม Greedy

เริ่มจากธนบัตรมากที่สุด ใช้มากที่สุดเท่าที่จะเป็นไปได้ แล้วค่อยลงมาลงมา

ทำงานได้ถูกต้องเพราะชุดธนบัตรเป็น Canonical Coin System

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

#include <iostream>
using namespace std;

void countNotes(int amount) {
    int notes[] = {2000, 500, 200, 100, 50, 20, 10, 5, 2, 1};
    int freq[10] = {0};

    for (int i = 0; i < 10; i++) {
        if (amount >= notes[i]) {
            freq[i] = amount / notes[i];
            amount -= freq[i] * notes[i];
        }
    }

    cout << "Note count:\n";
    for (int i = 0; i < 10; i++) {
        if (freq[i] != 0)
            cout << notes[i] << " : " << freq[i] << endl;
    }
}

int main() {
    int amount = 1072;
    cout << "Total amount is: " << amount << endl;
    countNotes(amount);
    return 0;
}

ผลลัพธ์

Total amount is: 1072
Note count:
500 : 2
50 : 1
20 : 1
2 : 1

ความซับซ้อน

เวลา: O(k) โดย k = จำนวนประเภทธนบัตร (คงที่), พื้นที่: O(1)

ข้อควรระวัง

Greedy ไม่ได้ทำงานเสมอไปสำหรับชุดธนบัตรทั่วไป (เช่น {1, 3, 4} ทำ 6 → Greedy ให้ 4+1+1=3 ใบ แต่ Optimal คือ 3+3=2 ใบ) แต่ชุดไทย/สากลทำงานได้