โปรแกรม C/C++ อัลกอริทึมล้มลอย (Greedy) หาเหรียญ/ธนบัตรน้อยที่สุด

อัลกอริทึมล้มลอย (Greedy Algorithm)

ค้นหาคำตอบที่เหมาะสมที่สุดในท้องถิ่น (locally optimal) ทีละขั้นตอน เพื่อให้ได้คำตอบที่เหมาะสมที่สุดในภาพรวม (globally optimal)

โจทย์

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

ตัวอย่าง

Input: 1231 → Output: 7 (500×2, 100×2, 20×1, 10×1, 1×1)
Input: 2150 → Output: 3 (2000×1, 100×1, 50×1)

อัลกอริทึม

เรียงหน่วยเงินจากมากไปน้อย
เลือกหน่วยเงินที่ใหญ่ที่สุดที่ ≤ จำนวนเงินคงเหลือ
ลบหน่วยเงินนั้นออกจากจำนวนเงิน เพิ่มจำนวนเหรียญ
ทำซ้ำจนจำนวนเงินเหลือ 0

โค้ดภาษา C++

#include <bits/stdc++.h>
using namespace std;

int notes[] = {1, 2, 5, 10, 20, 50, 100, 200, 500, 2000};
int n = sizeof(notes) / sizeof(notes[0]);

void minchange(int sum) {
    vector coins;
    for (int i = n - 1; i >= 0; i--) {
        while (sum >= notes[i]) {
            sum -= notes[i];
            coins.push_back(notes[i]);
        }
    }
    for (int i = 0; i < coins.size(); i++)
        cout << coins[i] << "\t";
}

int main() {
    int n = 3253;
    cout << "The minimum number of coins/notes that sum up " << n << " is \t ";
    minchange(n);
    return 0;
}

ผลลัพธ์

2000  500  500  200  50  2  1

หมายเหตุ: อัลกอริทึมล้มลอยทำงานได้ถูกต้องสำหรับระบบเงินตราทั่วไป แต่ไม่รับประกันคำตอบที่เหมาะสมที่สุดสำหรับระบบหน่วยเงินที่กำหนดเองบางระบบ