Giảm Thiểu Đồng Xu (CSES 1634)
Đề bài
Hãy xét một hệ thống tiền bao gồm $n$ đồng xu. Mỗi đồng xu có giá trị là một số nguyên dương. Nhiệm vụ của bạn là tạo ra một khoản tiền $x$ bằng cách sử dụng các đồng xu có sẵn sao cho số lượng đồng xu là tối thiểu.
Ví dụ: nếu các đồng xu là $\{1, 5, 7\}$ và tổng mong muốn là $11$, một giải pháp tối ưu là $5 + 5 + 1$, cần $3$ đồng xu.
Input
- Dòng đầu vào đầu tiên có hai số nguyên $n$ và $x$: số lượng đồng xu và tổng số tiền mong muốn.
- Dòng thứ hai có $n$ số nguyên phân biệt $c_1, c_2, \dots, c_n$: giá trị của mỗi đồng xu.
Output
- In một số nguyên: số lượng đồng xu tối thiểu. Nếu không thể tạo ra tổng mong muốn, hãy in $-1$.
Constraints
- $1 \le n \le 100$
- $1 \le x \le 10^6$
- $1 \le c_i \le 10^6$
3 11
1 5 73Lời mở đầu
Đây là một bài quy hoạch động kinh điển trong bộ đề CSES. Mình sẽ đi từ cách đơn giản nhất là vét cạn bằng đệ quy, rồi cải tiến thành quy hoạch động top-down (đệ quy có nhớ), rồi bottom-up (công thức truy hồi), và cuối cùng là một cách cài đặt chạy nhanh hơn nữa. Hy vọng mang đến được giá trị cho các bạn 😇.
Link này công khai, bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên LQDOJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Tóm tắtHiểu đề cho thật đơn giản
Trước tiên mình sẽ tóm tắt lại đề bài một cách đơn giản nhất để bạn nào chưa hiểu như sau:
Ví dụ: $n = 3$, $x = 11$, $c = \{1, 5, 7\}$. Ta sẽ lấy 2 đồng xu $5$ và 1 đồng xu $1$. Vậy ta chỉ cần dùng 3 đồng xu, output $= 3$.
Cách 1Vét cạn bằng đệ quy
Cách làm đơn giản nhất của bài này chính là vét cạn, chính là ta thử mọi trường hợp có thể đó. Ta sẽ thấy rằng ở ví dụ, để tạo ra được số tiền là $11$ thì ta cần tạo ra số tiền là $10$ hoặc $6$ hoặc $4$. Tại vì 3 đồng xu có giá trị $1, 5, 7$:
- nếu ta tạo ra được số tiền là $10$ thì lấy thêm 1 đồng xu $1$ là ta sẽ có tổng $11$;
- nếu ta tạo ra được số tiền là $6$ thì lấy thêm 1 đồng xu $5$ là có tổng $11$;
- nếu ta tạo ra được số tiền là $4$ thì lấy thêm 1 đồng xu $7$ là có tổng $11$.
Tương tự, để tạo ra số tiền $10$ ta cần tạo ra số tiền $9$ hoặc $5$ hoặc $3$… Từ đó ta thấy để tạo ra số tiền $x$ thì ta phải tạo được số tiền là $x - c[1]$ hoặc $x - c[2]$ hoặc … hoặc $x - c[n]$. Viết gọn lại: để tạo ra số tiền $x$ thì ta phải tạo được số tiền $x - c[i]$ $(1 \le i \le n)$.
Hai tầng đầu của cây đệ quy với $c = \{1, 5, 7\}$: Try(5) đã xuất hiện 2 lần, Try(3) cũng vậy, và càng xuống sâu càng trùng nhiều hơn.
Giờ ta cần biết số đồng xu phải dùng. Nếu ta tạo được số tiền $10$ thì số đồng xu để tạo ra $11$ $=$ (số đồng xu để tạo ra $10$) $+ 1$, ta $+1$ vì ta thêm 1 đồng xu $1$ vào. Tương tự với $6$ (thêm đồng $5$) và $4$ (thêm đồng $7$).
Vậy đến đây có bạn sẽ kết luận là số đồng xu tối thiểu để tạo ra $11$ $= \min$(số đồng xu tạo ra $10$ $+1$, số đồng xu tạo ra $6$ $+1$, số đồng xu tạo ra $4$ $+1$). Nhưng vậy là sai nha, vì để tạo ra số tiền $10$ ta có thể dùng 10 đồng $1$, hoặc 3 đồng $1$ và 1 đồng $7$, hoặc 2 đồng $5$… (rất nhiều cách). Ta đang cần số đồng xu tối thiểu để tạo ra $11$ thì ta cũng cần số đồng xu tối thiểu để tạo ra $10, 6, 4$ chứ. Rồi từ đó ta mới so sánh xem cách nào dùng ít đồng xu nhất được.
Gọi biến
cnt là số đồng xu tối thiểu để tạo ra $x$ thì cnt = min(cnt, tốithiểu(x - c[i]) + 1) với $1 \le i \le n$.Để code được theo ý tưởng trên, ta sẽ xây dựng hàm đệ quy như sau:
- Hàm
Try(n, x)trả về số đồng xu tối thiểu để tạo ra số tiền $x$ với hệ thống tiền có $n$ đồng xu. - Điều kiện dừng 1 –
x < 0: nếu $c[i] > x$ thì $x - c[i]$ sẽ âm, mà số tiền tạo ra từ các đồng xu thì không thể âm được. Nên ta trả về một giá trị tượng trưng là không hợp lệ. Ta đang tìm min nên trả về một giá trị rất lớn để không ảnh hưởng đến việc tính toán. Đồng xu bé nhất là $1$, số tiền lớn nhất là $10^6$, vậy tệ nhất cần $10^6$ đồng xu, giá trị trả về phải $> 10^6$, mình trả về $10^8$. - Điều kiện dừng 2 –
x == 0: số tiền $0$ ta tạo được bằng cách không lấy đồng xu nào, nên trả về $0$. - Xử lý chạy: khởi tạo
cnt = 1e8(lúc đầu chưa biết có tạo được $x$ không nên gán giá trị không hợp lệ, cũng là giá trị rất to để cập nhật min), rồi cho $i$ chạy từ $1$ tới $n$:cnt = min(cnt, Try(n, x - c[i]) + 1).
Try(...) + 1). Nếu trả về INT_MAX $= 2^{31} - 1$ (giá trị lớn nhất kiểu int lưu được) thì khi cộng thêm 1 sẽ bị tràn số, rất nguy hiểm nha. Nên ở đây mình trả về (int)1e8 $= 10^8$.Sau đây là source code của mình về ý tưởng trên cho anh em nào cần tham khảo nha:
Code vét cạn đệ quy – TLE
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
int c[105];
int Try(int n, int x) {
if(x < 0) {
return (int)1e8;
}
if(x == 0) {
return 0;
}
int cnt = (int)1e8;
for(int i = 1; i <= n; ++i) {
cnt = min(cnt, Try(n, x - c[i]) + 1);
}
return cnt;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, x;
cin >> n >> x;
for(int i = 1; i <= n; ++i) {
cin >> c[i];
}
int res = Try(n, x);
if(res == (int)1e8) {
res = -1;
}
cout << res;
return 0;
}import sys
sys.setrecursionlimit(10000)
INF = 10**8
def Try(n, x):
if x < 0:
return INF
if x == 0:
return 0
cnt = INF
for i in range(1, n + 1):
cnt = min(cnt, Try(n, x - c[i]) + 1)
return cnt
data = sys.stdin.read().split()
n, x = int(data[0]), int(data[1])
c = [0] + [int(v) for v in data[2:2 + n]]
res = Try(n, x)
if res == INF:
res = -1
print(res)Và nếu anh em không quen với điều kiện dừng if(x < 0) thì trước mỗi lần gọi đệ quy ta hãy kiểm tra đồng tiền ta đang định lấy phải $\le x$ đã. Vì để tạo ra số tiền $x$ thì đồng tiền dùng để tạo ra nó phải $\le x$ chứ. Hàm Try() sửa lại như thế này vẫn hoàn toàn đúng nha 😁:
int Try(int n, int x) {
if(x == 0) {
return 0;
}
int cnt = (int)1e8;
for(int i = 1; i <= n; ++i) {
if(c[i] <= x) {
cnt = min(cnt, Try(n, x - c[i]) + 1);
}
}
return cnt;
}Giải thích một số chỗ trong code
ios::sync_with_stdio(0); cin.tie(0);2 dòng đầu tiên của hàm main sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn đang code theo ngôn ngữ C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé), nên kinh nghiệm trong các bài cần nhập xuất nhiều thì ta nên sử dụng 2 dòng này. Trong bài này đầu vào chỉ có tầm 100 số nên các bạn không thêm vào cũng được, nhưng mình vẫn thêm vào vì đó là thói quen rồi nha. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé.int res = Try(n, x);ta tạo biếnresđể lưu kết quả: số đồng xu tối thiểu để tạo ra số tiền $x$ từ hệ thống tiền gồm $n$ đồng xu.if(res == (int)1e8) res = -1;vì $10^8$ tượng trưng cho việc không thể tạo ra số tiền $x$, mà đề bảo khi đó in ra $-1$. Nhiều bạn sợ nhỡ hàmTry()không trả về đúng $10^8$ thì sao? Nhìn vào biếncnt: lúc đầu bằng $10^8$, nếu không tạo được $x - c[i]$ thìTry(x - c[i])trả về $10^8$, lúc nàycnt = min(10^8, 10^8 + 1)vẫn $= 10^8$ thôi. Nếu hơi khó hiểu thì có cách khác: để tạo ra $x$ cần nhiều nhất $x$ đồng xu (đồng nhỏ nhất có thể là $1$), nên nếures > xthì chắc chắn không hợp lệ, gánres = -1.
Với cách trên chắc chắn ta sẽ bị TLE (Time Limit Exceeded – quá giới hạn thời gian): số lời gọi tăng theo hàm mũ. Tuy nhiên hãy vẫn nên cài đặt nó để sau này ta lấy nó làm công cụ kiểm tra tính chính xác cho cách làm tối ưu, hoặc biết đâu ta có thể cải tiến nó thành quy hoạch động top-down.
Cách 2Quy hoạch động top-down (đệ quy có nhớ)
Cách làm vét cạn sẽ gặp một vấn đề khiến nó bị chậm đi rất nhiều, đó chính là các bài toán con trùng lặp. Tức khi ta gặp một vấn đề ta đã tính rồi, ta lại đi tính lại nó, điều đó khiến ta tốn rất nhiều thời gian. Nhìn lại cây đệ quy ở trên: Try(4), Try(3)… bị gọi đi gọi lại rất nhiều lần.
Để giải quyết, ta dùng 1 mảng để lưu kết quả của hàm Try(n, x) lại, đây chính là phương pháp quy hoạch động top-down hay còn gọi là đệ quy có nhớ.
- Mỗi lần gọi đệ quy thì chỉ có biến $x$ thay đổi, còn $n$ thì không. Vậy ta chỉ cần một mảng 1 chiều
f[xMax]($xMax = 10^6 + 5$), khai báo toàn cục để tránh tràn bộ nhớ stack. Phần tửf[x]lưu kết quả củaTry(n, x). - Hàm
Try()không thể trả về giá trị âm, nên ta lấp đầy mảngf = -1, tượng trưng cho việc chưa tính. - Sau mục điều kiện dừng, nếu
f[x] != -1(đã tính rồi) thì chỉ việcreturn f[x]. Ngược lại thì đi tính như cũ, lưu kết quả vàof[x]rồi trả về.
Code quy hoạch động top-down – AC
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int xMax = (int)1e6 + 5;
int c[105];
int f[xMax];
int Try(int n, int x) {
if(x < 0) {
return (int)1e8;
}
if(x == 0) {
return 0;
}
if(f[x] != -1) {
return f[x];
}
int cnt = (int)1e8;
for(int i = 1; i <= n; ++i) {
cnt = min(cnt, Try(n, x - c[i]) + 1);
}
return f[x] = cnt;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, x;
cin >> n >> x;
for(int i = 1; i <= n; ++i) {
cin >> c[i];
}
fill(&f[1], &f[x + 1], -1);
int res = Try(n, x);
if(res == (int)1e8) {
res = -1;
}
cout << res;
return 0;
}import sys, threading
INF = 10**8
def main():
data = sys.stdin.read().split()
n, x = int(data[0]), int(data[1])
c = [0] + [int(v) for v in data[2:2 + n]]
f = [-1] * (x + 1)
def Try(x):
if x < 0:
return INF
if x == 0:
return 0
if f[x] != -1:
return f[x]
cnt = INF
for i in range(1, n + 1):
cnt = min(cnt, Try(x - c[i]) + 1)
f[x] = cnt
return cnt
res = Try(x)
if res == INF:
res = -1
print(res)
# đệ quy sâu tới x tầng nên phải tăng giới hạn đệ quy và kích thước stack
sys.setrecursionlimit(1 << 21)
threading.stack_size(1 << 27)
t = threading.Thread(target=main)
t.start()
t.join()Giải thích một số chỗ trong code
fill(&f[1], &f[x + 1], -1);câu lệnh này chính là lấp đầy mảngfbằng $-1$, từf[1]tớif[x].return f[x] = cnt;vừa gánf[x] = cntvừa trả về giá trị đó.
Trong trường hợp xấu nhất ta phải lấp đầy mảng f, với mỗi phần tử lại chạy một vòng for từ $1$ tới $n$, vậy cần $x \cdot n$ phép tính. Tệ nhất $x = 10^6$, $n = 100$ cần khoảng $10^8$ phép tính, với code trên là ta đã AC rồi nha.
Cách 3Quy hoạch động bottom-up (công thức truy hồi)
Ta đã có cách quy hoạch động top-down rồi thì ta cũng sẽ có cách quy hoạch động bottom-up, chính là anh em sẽ tạo ra công thức truy hồi đó. Cho anh em nào đã biết cơ bản về quy hoạch động rồi thì ta có 4 bước như sau:
fill(&f[1], &f[x + 1], (int)1e8);$$F[i] = \min\big(F[i],\ F[i - c[j]] + 1\big) \quad (1 \le j \le n,\ c[j] \le i)$$ Phải kiểm tra $c[j] \le i$ vì nhỡ $i - c[j]$ âm thì sao.
Để áp dụng công thức trên ta làm một vòng for(i) chạy từ $1$ tới $x$. Khi chạy như vậy ta luôn đảm bảo rằng $F[i - c[j]]$ (với $c[j] \le i$) đã được tính rồi, vì vòng for(i) đang chạy tăng dần mà.
Em nhập các đồng xu và số tiền $x$ rồi bấm Tiếp để xem bảng $F$ được lấp đầy từng ô:
Code quy hoạch động bottom-up – AC
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int xMax = (int)1e6 + 5;
int c[105], f[xMax];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, x;
cin >> n >> x;
for(int i = 1; i <= n; ++i) {
cin >> c[i];
}
f[0] = 0;
fill(&f[1], &f[x + 1], (int)1e8);
for(int i = 1; i <= x; ++i) {
for(int j = 1; j <= n; ++j) {
if(c[j] <= i) {
f[i] = min(f[i], f[i - c[j]] + 1);
}
}
}
if(f[x] == (int)1e8) {
f[x] = -1;
}
cout << f[x];
return 0;
}import sys
INF = 10**8
data = sys.stdin.read().split()
n, x = int(data[0]), int(data[1])
c = [int(v) for v in data[2:2 + n]]
f = [INF] * (x + 1)
f[0] = 0
for i in range(1, x + 1):
best = f[i]
for cj in c:
if cj <= i and f[i - cj] + 1 < best:
best = f[i - cj] + 1
f[i] = best
print(-1 if f[x] == INF else f[x])Giải thích một số chỗ trong code
if(f[x] == (int)1e8) f[x] = -1;nếu $F[x] = 10^8$ chứng tỏ không thể tạo ra số tiền $x$, mà đề bảo khi đó in ra $-1$. Hoặc các bạn có thể viết: nếuf[x] == (int)1e8thì in $-1$, ngược lại inf[x].
Với cách trên thì code của ta sẽ ăn ít bộ nhớ hơn và chạy nhanh hơn vì không phải tốn bộ nhớ và thời gian cho việc gọi đệ quy nữa. Nhưng cách trên vẫn chưa phải là cách nhanh nhất, vì vòng for của ta vẫn chạy khá nhiều. Giờ ta sẽ đến với một cách cải tiến hơn.
Cách 4Đảo vòng lặp: xét từng đồng xu
Ta vẫn dùng quy hoạch động bottom-up thôi. $F[j]$ vẫn là số xu tối thiểu để tạo ra số tiền $j$, $F[x]$ vẫn là kết quả, khởi tạo (trường hợp cơ sở) vẫn như vậy. Khác ở chỗ: với $i$ đồng xu đầu tiên thì để tạo ra số tiền $j$ ta cần tối thiểu bao nhiêu đồng xu.
- Vòng
for(i)ở ngoài chạy từ $1$ tới $n$ (tượng trưng cho việc ta đang xét $i$ đồng xu đầu tiên). - Với đồng xu $i$ thì số tiền nhỏ nhất nó có thể góp vào là $c[i]$, vậy vòng
for(j)bắt đầu từj = c[i]và chạy đến $x$. - Nếu có cách tạo ra số tiền $j - c[i]$ thì chắc chắn ta tạo được số tiền $j$ (thêm đồng $c[i]$ vào là được mà). Vậy ta kiểm tra
if(f[j - c[i]] != (int)1e8)rồi áp dụng công thức truy hồi vẫn như trên:f[j] = min(f[j], f[j - c[i]] + 1).
j chạy tăng dần nên lúc tính f[j] thì f[j - c[i]] có thể đã dùng chính đồng $c[i]$ rồi, nhờ vậy mỗi loại đồng xu được dùng bao nhiêu lần cũng được, đúng như đề bài. Đồng xu nào có $c[i] > x$ thì vòng for(j) không chạy lần nào, tự động bị bỏ qua.#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int xMax = (int)1e6 + 5;
int c[105], f[xMax];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, x;
cin >> n >> x;
for(int i = 1; i <= n; ++i) {
cin >> c[i];
}
f[0] = 0;
fill(&f[1], &f[x + 1], (int)1e8);
for(int i = 1; i <= n; ++i) {
for(int j = c[i]; j <= x; ++j) {
if(f[j - c[i]] != (int)1e8) {
f[j] = min(f[j], f[j - c[i]] + 1);
}
}
}
if(f[x] == (int)1e8) {
f[x] = -1;
}
cout << f[x];
return 0;
}import sys
INF = 10**8
data = sys.stdin.read().split()
n, x = int(data[0]), int(data[1])
c = [int(v) for v in data[2:2 + n]]
f = [INF] * (x + 1)
f[0] = 0
for ci in c:
for j in range(ci, x + 1):
if f[j - ci] != INF and f[j - ci] + 1 < f[j]:
f[j] = f[j - ci] + 1
print(-1 if f[x] == INF else f[x])Với cách trên thì code của ta sẽ chạy nhanh hơn nữa nha. Tuy về mặt lý thuyết độ phức tạp thời gian vẫn là $O(n \cdot x)$, nhưng trong thực tế sẽ có nhiều test ta chạy nhanh hơn: vòng trong bắt đầu từ $c[i]$ chứ không phải từ $1$, không còn câu lệnh if(c[j] <= i) bị kiểm tra vô ích, và vòng j duyệt mảng f liên tục nên truy cập bộ nhớ rất "thân thiện" với cache.
Nhận xét
Đăng nhận xét