#include <bits/stdc++.h> #define N 100 #define pii pair<int, int> using namespace std;…
- User
#include <bits/stdc++.h> #define N 100 #define pii pair<int, int> using namespace std; const int Smax = 10001; const int oo = 99999999; int f[Smax], x[N+2], dd[Smax]; pii a[N+2]; int n,s; bool cmp(pii x, pii y) { return x.first < y.first; } int main() { freopen("ATM.INP","r",stdin); freopen("ATM.OUT","w",stdout); cin >> n >> s; for (int i=1; i<=n; i++) { cin >> a[i].first; a[i].second = i; } sort(a+1,a+n+1,cmp); for (int j=1; j<=s; j++) { f[j] = oo; for (int i=1; i<=n; i++) if (j >= a[i].first && f[j-a[i].first] < oo) { if (f[j] > f[j-a[i].first] + 1) { f[j] = f[j-a[i].first] + 1; dd[j] = i; } }
} int j = s, c = 0; while (j > 0) { x[a[dd[j]].second]++; j -= a[dd[j]].first; } cout << f[s] << endl; for (int i=1; i<=n; i++) a[a[i].second].first = x[i]; for (int i=1; i<=n; i++) cout << x[i] << " "; return 0;} dịch nghĩa của chương trình
- Assistant
Chương trình này liên quan đến một bài toán kinh điển trong lập trình, gọi là bài toán ATM, tương tự như bài toán đổi tiền (coin change problem). Dưới đây là dịch nghĩa chi tiết của chương trình:
-
Thư viện và định nghĩa:
#include <bits/stdc++.h> #define N 100 #define pii pair<int, int> using namespace std; const int Smax = 10001; const int oo = 99999999;#include <bits/stdc++.h>: Thư viện này bao gồm tất cả các thư viện chuẩn trong C++.#define N 100: Định nghĩa giới hạn số lượng mệnh giá.#define pii pair<int, int>: Định nghĩa một cặp số nguyên tiện lợi.Smaxvàoolà các hằng số định nghĩa kích thước tối đa của s và giá trị lớn (dùng khi không thể tìm thấy đáp án).
-
Biến và cấu trúc dữ liệu:
int f[Smax], x[N+2], dd[Smax]; pii a[N+2]; int n, s;f: Mảng lưu số lượng ít nhất các mệnh giá để tạo ra giá trị xác định.x: Mảng lưu số lượng mỗi mệnh giá dùng.dd: Mảng hỗ trợ để lưu lại chỉ số của tờ tiền mệnh giá được chọn cho mỗi giá trị.a: Mảng lưu các mệnh giá và chỉ số tương ứng.
-
Hàm so sánh:
bool cmp(pii x, pii y) { return x.first < y.first; }- Hàm so sánh dùng cho hàm
sort.
- Hàm so sánh dùng cho hàm
-
Hàm chính:
int main() { freopen("ATM.INP", "r", stdin); freopen("ATM.OUT", "w", stdout); cin >> n >> s; for (int i = 1; i <= n; i++) { cin >> a[i].first; a[i].second = i; } sort(a + 1, a + n + 1, cmp); for (int j = 1; j <= s; j++) { f[j] = oo; for (int i = 1; i <= n; i++) if (j >= a[i].first && f[j - a[i].first] < oo) { if (f[j] > f[j - a[i].first] + 1) { f[j] = f[j - a[i].first] + 1; dd[j] = i; } } } int j = s, c = 0; while (j > 0) { x[a[dd[j]].second]++; j -= a[dd[j]].first; } cout << f[s] << endl; for (int i = 1; i <= n; i++) a[a[i].second].first = x[i]; for (int i = 1; i <= n; i++) cout << x[i] << " "; return 0; }Chi tiết hàm
main:- Đọc file dữ liệu vào
ATM.INPvà ghi kết quả raATM.OUT. - Đọc vào số lượng mệnh giá và số tiền cần đổi.
- Đọc các mệnh giá và lưu vào mảng
a. - Sắp xếp mảng
atheo giá trị mệnh giá tăng dần. - Tính toán số lượng ít nhất các mệnh giá cần để tạo ra mỗi giá trị từ 1 đến
s:- Nếu số tiền
jcó thể tạo được từ một mệnh giá nào đó thì cập nhật số lượng mệnh giá cần thiết.
- Nếu số tiền
- Dùng
ddđể theo dõi mệnh giá nào được dùng để tạo ra số tiềns. - Xuất kết quả: số lượng các mệnh giá cần để tạo ra số tiền
svà số lượng mỗi mệnh giá được sử dụng.
- Đọc file dữ liệu vào
Nói một cách đơn giản, chương trình tìm cách tối ưu số lượng các tờ tiền để đạt được tổng số tiền
sdựa trên các mệnh giá cho trước. -