บทนำ
กำหนดชุดเหรียญ C(c1, c2, ..., Cn) และค่าเงิน V ต้องการหาจำนวนเหรียญน้อยที่สุดที่รวมกันได้ค่า V โดยสมมติว่าเหรียญแต่ละประเภทมีจำนวนไม่จำกัด
ในตัวอย่างนี้ใช้ชุดเหรียญ {1, 2, 5, 10} เช่น สำหรับค่า 22 จะเลือก {10, 10, 2} ใช้ 3 เหรียญ
ความซับซ้อนของเวลา (Time Complexity)
O(V) โดยที่ V คือค่าเงินที่ต้องการทอน
อินพุตและเอาต์พุต
Input: ค่าเงิน เช่น 47 Output: Enter value: 47 Coins are: 10, 10, 10, 10, 5, 2
อัลกอริทึม (Greedy Approach)
findMinCoin(value)
Input: ค่าเงินที่ต้องการทอน
Output: ชุดเหรียญที่ใช้
Begin
coins set := {1, 2, 5, 10}
สำหรับเหรียญ i จากค่าสูงไปต่ำ do
while value >= coins[i] do
value := value - coins[i]
เพิ่ม coins[i] เข้าในรายการเหรียญ
done
done
แสดงรายการเหรียญทั้งหมด
End
ตัวอย่างโค้ด (C++)
#include<iostream>
#include<list>
#define COINS 4
using namespace std;
float coins[COINS] = {1, 2, 5, 10};
void findMinCoin(int cost) {
list<int> coinList;
for(int i = COINS-1; i>=0; i--) {
while(cost >= coins[i]) {
cost -= coins[i];
coinList.push_back(coins[i]); // เพิ่มเหรียญในลิสต์
}
}
list<int>::iterator it;
for(it = coinList.begin(); it != coinList.end(); it++) {
cout << *it << ", ";
}
}
main() {
int val;
cout << "Enter value: ";
cin >> val;
cout << "Coins are: ";
findMinCoin(val);
cout << endl;
}
ผลลัพธ์
Enter value: 47 Coins are: 10, 10, 10, 10, 5, 2
