อัลกอริธึมโลภคืออัลกอริธึมที่ใช้เพื่อค้นหาวิธีแก้ปัญหาที่เหมาะสมที่สุดสำหรับปัญหาที่กำหนด อัลกอริธึมที่โลภทำงานโดยค้นหาวิธีแก้ปัญหาที่เหมาะสมที่สุดในพื้นที่ (วิธีแก้ปัญหาที่เหมาะสมที่สุดสำหรับส่วนหนึ่งของปัญหา) ของแต่ละส่วน เพื่อแสดงวิธีแก้ปัญหาที่เหมาะสมที่สุดทั่วโลก
ในปัญหานี้ เราจะใช้อัลกอริธึมที่โลภเพื่อค้นหาจำนวนเหรียญ/ธนบัตรขั้นต่ำที่สามารถนำมารวมกับผลรวมที่กำหนดได้ สำหรับสิ่งนี้ เราจะพิจารณาเหรียญหรือธนบัตรที่ถูกต้องทั้งหมด เช่น นิกาย { 1, 2, 5, 10, 20, 50 , 100, 200 , 500 ,2000 } และเราจำเป็นต้องคืนจำนวนเหรียญ/ธนบัตรที่เราต้องใช้คืนเป็นยอดรวม
มาดูตัวอย่างเพื่อทำความเข้าใจบริบทกันดีกว่า −
ตัวอย่างที่ 1 -
Input : 1231 Output : 7
คำอธิบาย − เราต้องการธนบัตร Rs 500 สองฉบับ ธนบัตร Rs 100 สองฉบับ ธนบัตร Rs 20 ฉบับ 1 ฉบับ ธนบัตร Rs 10 ฉบับ 1 ฉบับ และเหรียญ Re 1 หนึ่งเหรียญ ซึ่งรวมเป็น 2+2+1+1+1 =7
ตัวอย่างที่ 2 -
Input : 2150 Output : 3
คำอธิบาย - เราต้องการธนบัตร 2,000 รูปี 1 ฉบับ ธนบัตร 100 รูปี 1 ฉบับ และธนบัตร 50 รูปีหนึ่งฉบับ
เพื่อแก้ปัญหานี้โดยใช้อัลกอริธึมที่โลภ เราจะหาว่าอันไหนเป็นนิกายที่ใหญ่ที่สุดที่สามารถใช้ได้ จากนั้นเราจะลบจำนวนเงินที่ใหญ่ที่สุดออกจากผลรวมและทำขั้นตอนเดียวกันอีกครั้งจนกว่าผลรวมจะกลายเป็นศูนย์
อัลกอริทึม
Input: sum, Initialise the coins = 0 Step 1: Find the largest denomination that can be used i.e. smaller than sum. Step 2: Add denomination two coins and subtract it from the Sum Step 3: Repeat step 2 until the sum becomes 0. Step 4: Print each value in coins.
ตัวอย่าง
#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<int> 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;
} ผลลัพธ์
The minimum number of coins/notes that sum up 3253 is 2000 500 500 200 50 2 1
