Thuật toán tham lam là một thuật toán được sử dụng để tìm ra một giải pháp tối ưu cho bài toán đã cho. Thuật toán tham lam hoạt động bằng cách tìm các giải pháp tối ưu cục bộ (giải pháp tối ưu cho một phần của vấn đề) của mỗi phần, do đó, có thể tìm thấy giải pháp tối ưu Toàn cục.
Trong bài toán này, chúng tôi sẽ sử dụng một thuật toán tham lam để tìm số lượng tiền / tờ tiền tối thiểu có thể tạo thành tổng đã cho. Đối với điều này, chúng tôi sẽ xem xét tất cả các đồng xu hoặc tiền giấy hợp lệ, tức là các mệnh giá {1, 2, 5, 10, 20, 50, 100, 200, 500, 2000}. Và chúng tôi cần trả lại số xu / ghi chú này mà chúng tôi sẽ cần để tạo thành tổng.
Hãy lấy một vài ví dụ để hiểu ngữ cảnh tốt hơn -
Ví dụ 1 -
Input : 1231 Output : 7
Giải thích - Chúng tôi sẽ cần hai tờ tiền 500 Rs, hai tờ 100 Rs, một tờ 20 Rs, một tờ 10 Rs và một đồng Re 1. Tổng thành 2 + 2 + 1 + 1 + 1 =7
Ví dụ 2 -
Input : 2150 Output : 3
Giải thích - Chúng tôi sẽ cần một tờ tiền 2000 Rs, một tờ 100 Rs và một tờ 50 Rs.
Để giải quyết vấn đề này bằng cách sử dụng thuật toán tham lam, chúng ta sẽ tìm mệnh giá lớn nhất có thể được sử dụng. sau đó chúng ta sẽ lấy tổng trừ đi mệnh giá lớn nhất và thực hiện lại quy trình tương tự cho đến khi tổng bằng không.
Thuật toán
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.
Ví dụ
#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;
} Đầu ra
The minimum number of coins/notes that sum up 3253 is 2000 500 500 200 50 2 1