Money Sum

Nguồn: CSES Problem Set (LQDOJ) Độ khó: Trung bình Quy hoạch động Đệ quy có nhớ Vét cạn

Đề bài

CSES – Money Sums | Khoản tiền

Bạn có $n$ đồng xu với các mệnh giá nhất định. Nhiệm vụ của bạn là tìm tất cả các khoản tiền có thể tạo ra bằng những đồng xu này.

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên $n$: số lượng đồng xu.
• Dòng tiếp theo chứa $n$ số nguyên $x_1, x_2, \ldots, x_n$: mệnh giá của các đồng xu.

Kết quả: Đầu tiên in ra một số nguyên $k$: số lượng khoản tiền phân biệt. Sau đó in ra tất cả các khoản tiền có thể tạo ra theo thứ tự tăng dần.

Ràng buộc: $1 \le n \le 100$, $1 \le x_i \le 1000$.

Giới hạn: thời gian 1 giây, bộ nhớ 512 MB.

Ví dụ – input

4
4 2 5 2

Ví dụ – output

9
2 4 5 6 7 8 9 11 13

Lời mở đầu

Đây là một bài quy hoạch động kinh điển trong bộ CSES. Bài này rất hợp để luyện đúng một "lộ trình" mà mình hay dạy: vét cạn bằng đệ quy → đệ quy có nhớ (quy hoạch động top-down) → quy hoạch động bottom-up (công thức truy hồi) → rút gọn mảng 2 chiều về 1 chiều. Mình viết lời giải chi tiết đủ cả 4 bước để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Trước tiên mình 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: cho $n$ đồng xu có giá trị $a[1], a[2], \ldots, a[n]$. Ta cần tìm tất cả các khoản tiền có thể tạo ra bằng cách chọn ra một số đồng xu (ít nhất 1 đồng), mỗi đồng xu chỉ được dùng tối đa 1 lần. In ra số khoản tiền phân biệt, rồi in các khoản tiền đó theo thứ tự tăng dần.

Mình giải thích ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ. Có 4 đồng xu $4, 2, 5, 2$ (tổng là $13$). Các khoản tiền tạo được:

Khoản tiền	Một cách chọn
2	2
4	4 (hoặc 2 + 2)
5	5
6	4 + 2
7	5 + 2
8	4 + 2 + 2
9	4 + 5 (hoặc 5 + 2 + 2)
11	4 + 5 + 2
13	4 + 2 + 5 + 2 (lấy hết)
1, 3, 10, 12	không có cách chọn nào

Vậy có $9$ khoản tiền phân biệt: 2 4 5 6 7 8 9 11 13. Để ý khoản tiền $4$ có 2 cách tạo nhưng chỉ tính 1 lần thôi nha (đề hỏi khoản tiền phân biệt).

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Vét cạn đệ quy · TLE (6/12 test)Cách 2Đệ quy có nhớ · O(n·sum) · ACCách 3QHĐ bottom-up · O(n·sum) · ACCách 4Mảng 1 chiều · bộ nhớ O(sum)

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, tức ta thử hết mọi trường hợp có thể. Đầu tiên ta nhận xét:

• Số tiền lớn nhất tạo được là tổng của tất cả $n$ đồng xu (ở ví dụ là $4 + 2 + 5 + 2 = 13$). Điều đó là hiển nhiên rồi.
• Số tiền nhỏ nhất tạo được chính là đồng xu có giá trị nhỏ nhất (ở ví dụ là $2$).

Vậy số tiền tạo ra được chỉ có thể nằm trong khoảng từ giá trị đồng xu nhỏ nhất đến tổng của $n$ đồng xu. Giờ ta cần một hàm cho ta biết: dùng $n$ đồng xu đầu tiên thì có thể tạo ra số tiền là $val$ không? Rồi ta duyệt một vòng for từ giá trị nhỏ nhất đến tổng, với mỗi số tiền ta dùng hàm để kiểm tra.

Ta xây dựng hàm đệ quy như sau:

Hàm Try(n, val)

Try(n, val) trả về true nếu dùng $n$ đồng xu đầu tiên có thể tạo ra số tiền đúng bằng $val$ (mỗi đồng dùng tối đa 1 lần), ngược lại trả về false.

Điều kiện dừng:

1. Khi số tiền cần tạo $val = 0$ thì ta luôn tạo được, vì chỉ cần không lấy đồng xu nào là có số tiền $0$. Vậy if(val == 0) return true;
2. Khi $val \gt 0$ mà ta lại không còn đồng xu nào để chọn ($n = 0$) thì chắc chắn không tạo được, vì không xét đồng xu nào thì đâu thể tạo ra số tiền lớn hơn $0$. Vậy if(n == 0) return false;

Xử lý chạy: giả sử ta đang xét đồng xu thứ $n$. Ta khởi tạo biến res lưu kết quả của Try(n, val). Có 2 trường hợp:

1. Không chọn đồng xu thứ $n$: lúc này chỉ còn $n - 1$ đồng xu đầu tiên, số tiền cần tạo vẫn là $val$. Kết quả trường hợp này là Try(n - 1, val). Trường hợp này không cần thêm điều kiện gì nên ta gán luôn res = Try(n - 1, val).
2. Có chọn đồng xu thứ $n$: cần thoả 2 điều kiện:
   • res vẫn đang là false. Nếu res = true rồi (tạo được $val$ mà không cần đồng xu thứ $n$) thì việc gì phải thử thêm; thử nữa vừa tốn thời gian, mà nhỡ trường hợp chọn đồng xu thứ $n$ không tạo được thì res đang true lại bị gán thành false – sai kết quả luôn.
   • $val \ge a[n]$: số tiền cần tạo phải lớn hơn hoặc bằng đồng xu định chọn. Ta không thể chọn đồng xu giá trị $4$ khi đang cần tạo số tiền $2$ được.
   Khi thoả cả 2 điều kiện: để tạo ra $val$ mà có lấy đồng xu thứ $n$, ta cần biết với $n - 1$ đồng xu đầu tiên có tạo ra được số tiền $val - a[n]$ hay không. Tạo được thì chỉ việc thêm đồng xu thứ $n$ (giá trị $a[n]$) vào là có đúng $val$; không tạo được thì trường hợp này cũng không tạo được $val$. Và đó chính là Try(n - 1, val - a[n]).

Code phần xử lý

bool res = Try(n - 1, val);
if(!res && val >= a[n]) res = Try(n - 1, val - a[n]);
return res;

if(!res) là gì?

if(!res) chính là if(res == false) đó. Trong C++, khi viết if(res) thì nó hiểu là if(res != 0) hay chính là res == true. Thêm dấu ! (phủ định) vào thì bị đảo ngược lại, tức là res == false.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

int a[105];

bool Try(int n, int val) {
    if(val == 0) {
        return true;
    }
    if(n == 0) {
        return false;
    }
    bool res = Try(n - 1, val);
    if(!res && val >= a[n]) {
        res = Try(n - 1, val - a[n]);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    int sum = 0;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum += a[i];
    }
    vector<int> res;
    for(int i = *min_element(a + 1, a + n + 1); i <= sum; ++i) {
        if(Try(n, i)) {
            res.push_back(i);
        }
    }
    cout << (int)res.size() << endl;
    for(int x : res) {
        cout << x << " ";
    }
    return 0;
}

import sys
sys.setrecursionlimit(10000)

def Try(n, val):
    if val == 0:
        return True
    if n == 0:
        return False
    res = Try(n - 1, val)
    if not res and val >= a[n]:
        res = Try(n - 1, val - a[n])
    return res

data = sys.stdin.read().split()
n = int(data[0])
a = [0] * (n + 1)
total = 0
for i in range(1, n + 1):
    a[i] = int(data[i])
    total += a[i]
res = []
for i in range(min(a[1:]), total + 1):
    if Try(n, i):
        res.append(i)
print(len(res))
print(*res)

Các bạn bấm Tiếp để chạy tay từng dòng; ngăn xếp lời gọi đệ quy hiện ở phần "Dữ liệu". Thử nút 3 đồng: 1 2 3 để xem cùng một lời gọi như Try(1, 1) bị tính đi tính lại nhiều lần như thế nào nha.

C++▶ Chạy tay từng dòng codeCách 1: với mỗi số tiền i từ min đến sum, gọi Try(n, i): bỏ qua hoặc chọn đồng xu thứ n.

Dữ liệu vào (stdin) – sửa thoải mái4 4 2 5 2

Dữ liệu mẫu:

1#include<bits/stdc++.h>

2#define endl '\n'

3

4using namespace std;

5typedef long long ll;

6

7int a[105];

8

9bool Try(int n, int val) {

10 if(val == 0) {

11 return true;

12 }

13 if(n == 0) {

14 return false;

15 }

16 bool res = Try(n - 1, val);

17 if(!res && val >= a[n]) {

18 res = Try(n - 1, val - a[n]);

19 }

20 return res;

21}

22

23int main() {

24 ios::sync_with_stdio(0);

25 cin.tie(0);

26

27 int n;

28 cin >> n;

29 int sum = 0;

30 for(int i = 1; i <= n; ++i) {

31 cin >> a[i];

32 sum += a[i];

33 }

34 vector<int> res;

35 for(int i = *min_element(a + 1, a + n + 1); i <= sum; ++i) {

36 if(Try(n, i)) {

37 res.push_back(i);

38 }

39 }

40 cout << (int)res.size() << endl;

41 for(int x : res) {

42 cout << x << " ";

43 }

44 return 0;

45}

ChậmVừaNhanhRất nhanh

Giải thích 1 số chỗ trong code ở trên:

1. Biến sum lưu tổng giá trị của $n$ đồng xu. Có tối đa $100$ đồng xu, mỗi đồng tối đa $1000$ nên tổng tối đa là $100 \cdot 1000 = 10^5$ – kiểu int (chứa được tới $2^{31} - 1$) là thoải mái.
2. vector<int> res: dùng vector để lưu kết quả, vừa tiện biết có bao nhiêu khoản tiền (res.size()), vừa tiện in ra các khoản tiền.
3. *min_element(a + 1, a + n + 1): hàm min_element(start, end) trả về con trỏ trỏ đến phần tử nhỏ nhất trong đoạn từ start đến trước end, nên thêm dấu * ta được giá trị nhỏ nhất trong $a[1..n]$. Bạn nào không biết hàm này thì tạo biến minA = INT_MAX rồi cập nhật luôn lúc đọc dữ liệu cũng được, độ phức tạp đều là $O(n)$.
4. for(int x : res): vòng lặp for-each, lần lượt gán $x$ bằng từng phần tử của res. Không quen thì duyệt bằng chỉ số như bình thường cũng được nha.

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(n)$ cho mảng $a$ và độ sâu đệ quy (tối đa $n$ tầng), cộng vector kết quả $O(sum)$.
• Thời gian: mỗi lời gọi Try có thể tách thành 2 lời gọi con, nên một lần Try(n, i) tệ nhất tốn $O(2^n)$; nhân với số khoản tiền phải thử (tới $sum$) là $O(sum \cdot 2^n)$.

Không gian$O(n + sum)$

Thời gian$O(sum \cdot 2^n)$

Chắc chắn TLE

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), cụ thể ăn được 6/12 test. Mình đo thử bản C++: với $n = 20$ đồng xu ngẫu nhiên đã mất khoảng 2.4 giây, $n = 25$ chạy quá 60 giây vẫn chưa xong, trong khi đề cho $n$ tới $100$. Tuy nhiên các bạn vẫn nên cài đặt nó: vừa để làm công cụ kiểm tra tính chính xác cho cách tối ưu (sinh test nhỏ rồi so kết quả), vừa vì từ nó ta cải tiến ngay được thành quy hoạch động top-down ở cách 2.

Cách 2Đệ quy có nhớ (QHĐ top-down) – O(n·sum)

Lý do code ở trên chạy lâu chính là: nếu ta đã tính một vấn đề rồi mà lần sau gặp lại thì vẫn phải đi tính lại nó. Việc tính đi tính lại này khiến ta tốn rất nhiều thời gian (các bạn bấm nút 3 đồng: 1 2 3 ở khung chạy tay trên sẽ thấy). Tư tưởng của đệ quy có nhớ là dùng một kiểu dữ liệu (mảng, vector, map…) để lưu lại những kết quả đã tính; gặp lại vấn đề đã tính thì chỉ việc trả về kết quả, không phải tính lại nữa. Ta làm 3 bước như sau:

1Tham số nào thay đổi? Hàm Try(n, val) có 2 tham số và cả 2 đều thay đổi ở mỗi lần gọi đệ quy. Vậy ta tạo mảng 2 chiều $F$, với $F[n][val]$ lưu kết quả của Try(n, val).

2Giới hạn của tham số? $n$ tối đa $100$, $val$ tối đa là $sum \le 10^5$. Vậy khai báo f[105][(int)1e5 + 5] – mình hay cộng thêm 5 để thừa vài phần tử, tránh truy cập ra ngoài mảng.

3Giá trị không thể trả về? Hàm kiểu bool chỉ trả về true/false (tức $1$/$0$), không bao giờ trả về $-1$. Nên ta khai báo $F$ kiểu int và lấp đầy bằng $-1$, nghĩa là "chưa tính".

✓Dùng như thế nào? Sau phần điều kiện dừng, nếu f[n][val] != -1 thì đã tính rồi, trả về luôn. Ngược lại tính như bình thường, rồi gán f[n][val] = res trước khi trả về.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

int a[105];
int f[105][(int)1e5 + 5];

bool Try(int n, int val) {
    if(val == 0) {
        return true;
    }
    if(n == 0) {
        return false;
    }
    if(f[n][val] != -1) {
        return f[n][val];
    }
    bool res = Try(n - 1, val);
    if(!res && val >= a[n]) {
        res = Try(n - 1, val - a[n]);
    }
    return f[n][val] = res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    int sum = 0;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum += a[i];
    }
    fill(&f[1][1], &f[n][sum + 1], -1);
    vector<int> res;
    for(int i = *min_element(a + 1, a + n + 1); i <= sum; ++i) {
        if(Try(n, i)) {
            res.push_back(i);
        }
    }
    cout << (int)res.size() << endl;
    for(int x : res) {
        cout << x << " ";
    }
    return 0;
}

import sys
sys.setrecursionlimit(10000)

def Try(n, val):
    if val == 0:
        return True
    if n == 0:
        return False
    if f[n][val] != -1:
        return f[n][val] == 1
    res = Try(n - 1, val)
    if not res and val >= a[n]:
        res = Try(n - 1, val - a[n])
    f[n][val] = 1 if res else 0
    return res

data = sys.stdin.read().split()
n = int(data[0])
a = [0] * (n + 1)
total = 0
for i in range(1, n + 1):
    a[i] = int(data[i])
    total += a[i]
f = [[-1] * (total + 1) for _ in range(n + 1)]
res = []
for i in range(min(a[1:]), total + 1):
    if Try(n, i):
        res.append(i)
print(len(res))
print(*res)

Trong khung chạy tay dưới đây, phần "Dữ liệu" có thêm bảng $f$ (hàng = $n$, cột = $val$; ô trống là $-1$ – chưa tính). Các bạn để ý những lần ô màu xanh được "lấy ra dùng lại" ngay mà không phải gọi đệ quy tiếp nha:

C++▶ Chạy tay từng dòng codeCách 2: như cách 1 nhưng lưu Try(n, val) vào f[n][val], gặp lại thì trả về luôn.

Dữ liệu vào (stdin) – sửa thoải mái4 4 2 5 2

Dữ liệu mẫu:

1#include<bits/stdc++.h>

2#define endl '\n'

3

4using namespace std;

5typedef long long ll;

6

7int a[105];

8int f[105][(int)1e5 + 5];

9

10bool Try(int n, int val) {

11 if(val == 0) {

12 return true;

13 }

14 if(n == 0) {

15 return false;

16 }

17 if(f[n][val] != -1) {

18 return f[n][val];

19 }

20 bool res = Try(n - 1, val);

21 if(!res && val >= a[n]) {

22 res = Try(n - 1, val - a[n]);

23 }

24 return f[n][val] = res;

25}

26

27int main() {

28 ios::sync_with_stdio(0);

29 cin.tie(0);

30

31 int n;

32 cin >> n;

33 int sum = 0;

34 for(int i = 1; i <= n; ++i) {

35 cin >> a[i];

36 sum += a[i];

37 }

38 fill(&f[1][1], &f[n][sum + 1], -1);

39 vector<int> res;

40 for(int i = *min_element(a + 1, a + n + 1); i <= sum; ++i) {

41 if(Try(n, i)) {

42 res.push_back(i);

43 }

44 }

45 cout << (int)res.size() << endl;

46 for(int x : res) {

47 cout << x << " ";

48 }

49 return 0;

50}

ChậmVừaNhanhRất nhanh

Giải thích 1 số chỗ trong code ở trên:

1. return f[n][val] = res; chính là gán f[n][val] = res rồi return f[n][val].
2. fill(&f[1][1], &f[n][sum + 1], -1); là thao tác lấp đầy mảng $F$ bằng $-1$ (mảng 2 chiều nằm liên tiếp trong bộ nhớ nên fill từ địa chỉ ô đầu tới ô cuối là được). Bạn nào không biết hàm fill thì dùng 2 vòng for lồng nhau cũng được, độ phức tạp như nhau thôi.

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(n \cdot sum)$ với $sum$ là tổng giá trị $n$ đồng xu. Thực chất là $O(n \cdot sum + n)$ vì dùng mảng $f$ và mảng $a$, nhưng theo quy tắc Big-O thì là $O(n \cdot sum)$.
• Thời gian: $O(n \cdot sum)$, vì trường hợp tệ nhất ta phải lấp đầy toàn bộ mảng $F$, mỗi ô tính một lần mất $O(1)$.

Không gian$O(n \cdot sum)$

Thời gian$O(n \cdot sum)$

Với $n = 100$, $sum = 10^5$ thì cỡ $10^7$ phép tính – cách này đã AC bài rồi. Tuy nhiên thời gian chạy vẫn còn khá lâu do phải tốn thời gian và bộ nhớ cho việc gọi đệ quy, và bộ nhớ cũng ăn nhiều (mảng int $105 \times 100005$ khoảng 40 MB).

Cách 3Quy hoạch động bottom-up – O(n·sum)

Ta cải tiến hơn bằng quy hoạch động bottom-up, tức là anh em sẽ tạo ra công thức truy hồi và tính bằng vòng lặp. 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:

1Bài toán con: $F[i][j]$ cho biết với $i$ đồng xu đầu tiên có tạo ra được khoản tiền $j$ hay không (true/false).

2Bài toán cơ sở: $F[i][0] = \text{true}$ với $0 \le i \le n$; $F[0][j] = \text{false}$ với $1 \le j \le sum$.

3Đáp án: mọi $j$ ($1 \le j \le sum$) có $F[n][j] = \text{true}$.

4Truy hồi: $F[i][j] = F[i-1][j]$; nếu $F[i][j] = \text{false}$ và $j \ge a[i]$ thì $F[i][j] = F[i-1][j-a[i]]$.

Bước 1: Xác định bài toán con

Gọi $F[i][j]$ cho ta biết với $i$ đồng xu đầu tiên thì ta có thể tạo ra khoản tiền $j$ được hay không. $F[i][j] = \text{true}$ tức là tạo được; ngược lại $F[i][j] = \text{false}$ là không tạo được.

Bước 2: Xác định bài toán cơ sở

Khi số tiền cần là $0$ ($j = 0$) thì ta luôn tạo được, vì chỉ cần không chọn đồng xu nào. Vậy $F[i][0] = \text{true}$ với $0 \le i \le n$.

Khi không xét đồng xu nào ($i = 0$) mà khoản tiền cần lại lớn hơn $0$ thì dĩ nhiên không tạo được. Vậy $F[0][j] = \text{false}$ với $1 \le j \le sum$.

Cho tiện, ta khai báo mảng $F$ là mảng toàn cục thì các phần tử được khởi tạo sẵn bằng $0$ (tức false), rồi chỉ cần một vòng for gán $F[i][0] = \text{true}$ là xong.

Bước 3: Xác định đáp án của bài toán

Ta cần biết với $n$ đồng xu thì tạo ra được những khoản tiền nào. Duyệt $j$ từ $1$ tới $sum$: nếu $F[n][j] = \text{true}$ thì lưu $j$ vào vector kết quả. Vì $j$ duyệt tăng dần nên các khoản tiền tự động theo thứ tự tăng dần luôn.

Bước 4: Xác định công thức truy hồi

Tại đây ta có 2 trường hợp (giống hệt 2 trường hợp của hàm Try):

1. Không chọn đồng xu thứ $i$: để tạo ra $j$ thì chỉ được dùng $i - 1$ đồng xu đầu tiên, đó chính là $F[i-1][j]$. Suy ra $F[i][j] = F[i-1][j]$.
2. Có chọn đồng xu thứ $i$: cũng phải thoả 2 điều kiện: $F[i][j]$ đang là false (trường hợp 1 đã true thì khỏi xét) và $j \ge a[i]$ (không thể lấy đồng xu $5$ khi số tiền cần là $4$). Khi đó cần biết với $i - 1$ đồng đầu có tạo ra $j - a[i]$ không – chính là $F[i-1][j-a[i]]$. Tạo được thì thêm đồng thứ $i$ vào là có đúng $j$.

Công thức truy hồi

$F[i][j] = F[i-1][j]$.
Nếu $F[i][j] = \text{false}$ và $j \ge a[i]$: $F[i][j] = F[i-1][j - a[i]]$.
Gọn lại: $F[i][j] = F[i-1][j] \ \text{OR}\ \big(j \ge a[i] \ \text{AND}\ F[i-1][j-a[i]]\big)$.

Nhìn trên bảng thì ô $(i, j)$ chỉ phụ thuộc vào 2 ô ở hàng ngay trên: ô thẳng phía trên $(i-1, j)$ và ô lùi sang trái $a[i]$ cột $(i-1, j-a[i])$.

Minh hoạ: lấp bảng F từng ô

Các bạn nhập các đồng xu rồi bấm Tiếp. Ô vàng là ô đang tính, ô tím là ô phía trên $(i-1, j)$, ô cam viền là ô $(i-1, j-a[i])$. Bước cuối tô xanh các khoản tiền tạo được ở hàng $n$:

Các đồng xu a

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

int a[105];
bool f[105][(int)1e5 + 5];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    int sum = 0;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum += a[i];
    }
    for(int i = 0; i <= n; ++i) {
        f[i][0] = true;
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= sum; ++j) {
            f[i][j] = f[i - 1][j];
            if(!f[i][j] && j >= a[i]) {
                f[i][j] = f[i - 1][j - a[i]];
            }
        }
    }
    vector<int> res;
    for(int j = 1; j <= sum; ++j) {
        if(f[n][j]) {
            res.push_back(j);
        }
    }
    cout << (int)res.size() << endl;
    for(int x : res) {
        cout << x << " ";
    }
    return 0;
}

import sys

data = sys.stdin.read().split()
n = int(data[0])
a = [0] * (n + 1)
total = 0
for i in range(1, n + 1):
    a[i] = int(data[i])
    total += a[i]
f = [[False] * (total + 1) for _ in range(n + 1)]
for i in range(n + 1):
    f[i][0] = True
for i in range(1, n + 1):
    for j in range(1, total + 1):
        f[i][j] = f[i - 1][j]
        if not f[i][j] and j >= a[i]:
            f[i][j] = f[i - 1][j - a[i]]
res = []
for j in range(1, total + 1):
    if f[n][j]:
        res.append(j)
print(len(res))
print(*res)

C++▶ Chạy tay từng dòng codeCách 3: lấp bảng f[i][j] theo từng hàng i, mỗi hàng duyệt j = 1..sum.

Dữ liệu vào (stdin) – sửa thoải mái4 4 2 5 2

Dữ liệu mẫu:

1#include<bits/stdc++.h>

2#define endl '\n'

3

4using namespace std;

5typedef long long ll;

6

7int a[105];

8bool f[105][(int)1e5 + 5];

9

10int main() {

11 ios::sync_with_stdio(0);

12 cin.tie(0);

13

14 int n;

15 cin >> n;

16 int sum = 0;

17 for(int i = 1; i <= n; ++i) {

18 cin >> a[i];

19 sum += a[i];

20 }

21 for(int i = 0; i <= n; ++i) {

22 f[i][0] = true;

23 }

24 for(int i = 1; i <= n; ++i) {

25 for(int j = 1; j <= sum; ++j) {

26 f[i][j] = f[i - 1][j];

27 if(!f[i][j] && j >= a[i]) {

28 f[i][j] = f[i - 1][j - a[i]];

29 }

30 }

31 }

32 vector<int> res;

33 for(int j = 1; j <= sum; ++j) {

34 if(f[n][j]) {

35 res.push_back(j);

36 }

37 }

38 cout << (int)res.size() << endl;

39 for(int x : res) {

40 cout << x << " ";

41 }

42 return 0;

43}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(n \cdot sum)$ với $sum$ là tổng giá trị của $n$ đồng xu.
• Thời gian: $O(n \cdot sum)$ vì ta phải lấp đầy mảng $F$.

Không gian$O(n \cdot sum)$

Thời gian$O(n \cdot sum)$

Dù độ phức tạp thời gian và không gian giống hệt cách top-down, nhưng code này chạy nhanh hơn và ăn ít bộ nhớ hơn rất nhiều (mảng bool thay vì int, và không tốn thời gian, bộ nhớ cho việc gọi đệ quy nữa). Mình đo bản C++ với $n = 100$, $sum$ gần $10^5$: cách 2 khoảng 0.3 giây, cách 3 chỉ khoảng 0.07 giây.

Cách 4Phần đọc thêm: rút gọn về mảng 1 chiều

Đến đây ta còn cải tiến được nữa: thay vì mảng 2 chiều thì chỉ dùng mảng 1 chiều. Độ phức tạp không gian giảm xuống rất nhiều, độ phức tạp thời gian giữ nguyên, nhưng thời gian chạy thực tế vẫn nhanh hơn vì truy xuất mảng 1 chiều nhanh hơn mảng 2 chiều.

1. Bỏ chiều $[i]$: ở công thức cũ, $F[i][j]$ chỉ phụ thuộc vào hàng $[i-1]$. Vậy ta bỏ $[i]$ đi, chỉ còn mảng 1 chiều bool F[sum].
2. Cơ sở: $F[0][j] = \text{false}$ ($1 \le j \le sum$) thành $F[j] = \text{false}$ – khai báo mảng toàn cục là có sẵn. $F[i][0] = \text{true}$ thành $F[0] = \text{true}$.
3. Đáp án: sau khi chạy xong phần xử lý, $F[j]$ cho biết với $n$ đồng xu có tạo ra khoản tiền $j$ hay không. Chỉ cần một vòng for(j) kiểm tra $F[j]$.
4. Công thức truy hồi: để dễ hình dung, các bạn hiểu là trong lúc duyệt hàng $i$: ô đang xét và các ô chưa xét vẫn là giá trị của quá khứ (hàng $[i-1]$), còn các ô đã xét là giá trị của hiện tại (hàng $[i]$).
   • $F[i][j] = F[i-1][j]$ thành $F[j] = F[j]$ – khỏi làm gì luôn, vì $F[j]$ đang xét bản chất chính là $F[i-1][j]$ rồi.
   • $F[i][j] = F[i-1][j-a[i]]$ (khi $F[i][j] = \text{false}$ và $j \ge a[i]$) thành $F[j] = F[j - a[i]]$ (khi $F[j] = \text{false}$ và $j \ge a[i]$).

Chiều duyệt của j là mấu chốt

Nếu duyệt $j$ tăng dần thì $F[j - a[i]]$ là ô đã xét, tức là giá trị hiện tại $F[i][j - a[i]]$ – trong khi cái ta cần là $F[i-1][j - a[i]]$. Hậu quả là một đồng xu bị dùng nhiều lần (ví dụ có 2 đồng xu $2$ và $5$ thì chỉ tạo được $2, 5, 7$, nhưng duyệt tăng thì đồng xu $2$ được cộng tiếp vào chính nó, "tạo ra" thêm cả $4$ và $6$). Để giải quyết, ta duyệt ngược lại ($j$ giảm dần): khi đó $F[j - a[i]]$ là ô chưa xét, đúng là giá trị quá khứ $F[i-1][j - a[i]]$ mà ta cần. Kết hợp với điều kiện $j \ge a[i]$, vòng for(j) chạy ngược từ $sum$ về $a[i]$.

Minh hoạ: duyệt giảm (đúng) và duyệt tăng (sai)

Các bạn thử nút 2 5, duyệt tăng (sai) rồi so với 2 5, duyệt giảm sẽ thấy ngay vì sao phải duyệt ngược nha:

Các đồng xu a Chiều duyệt j (giam / tang)

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

int a[105];
bool f[(int)1e5 + 5];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    int sum = 0;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum += a[i];
    }
    f[0] = true;
    for(int i = 1; i <= n; ++i) {
        for(int j = sum; j >= a[i]; --j) {
            if(!f[j]) {
                f[j] = f[j - a[i]];
            }
        }
    }
    vector<int> res;
    for(int j = 1; j <= sum; ++j) {
        if(f[j]) {
            res.push_back(j);
        }
    }
    cout << (int)res.size() << endl;
    for(int x : res) {
        cout << x << " ";
    }
    return 0;
}

import sys

data = sys.stdin.read().split()
n = int(data[0])
a = [0] * (n + 1)
total = 0
for i in range(1, n + 1):
    a[i] = int(data[i])
    total += a[i]
f = [False] * (total + 1)
f[0] = True
for i in range(1, n + 1):
    for j in range(total, a[i] - 1, -1):
        if not f[j]:
            f[j] = f[j - a[i]]
res = []
for j in range(1, total + 1):
    if f[j]:
        res.append(j)
print(len(res))
print(*res)

C++▶ Chạy tay từng dòng codeCách 4: một mảng f[0..sum], mỗi đồng xu duyệt j giảm từ sum về a[i].

Dữ liệu vào (stdin) – sửa thoải mái4 4 2 5 2

Dữ liệu mẫu:

1#include<bits/stdc++.h>

2#define endl '\n'

3

4using namespace std;

5typedef long long ll;

6

7int a[105];

8bool f[(int)1e5 + 5];

9

10int main() {

11 ios::sync_with_stdio(0);

12 cin.tie(0);

13

14 int n;

15 cin >> n;

16 int sum = 0;

17 for(int i = 1; i <= n; ++i) {

18 cin >> a[i];

19 sum += a[i];

20 }

21 f[0] = true;

22 for(int i = 1; i <= n; ++i) {

23 for(int j = sum; j >= a[i]; --j) {

24 if(!f[j]) {

25 f[j] = f[j - a[i]];

26 }

27 }

28 }

29 vector<int> res;

30 for(int j = 1; j <= sum; ++j) {

31 if(f[j]) {

32 res.push_back(j);

33 }

34 }

35 cout << (int)res.size() << endl;

36 for(int x : res) {

37 cout << x << " ";

38 }

39 return 0;

40}

ChậmVừaNhanhRất nhanh

Giải thích 1 số chỗ trong code ở trên: đoạn for(int j = sum; j >= a[i]; --j) if(!f[j]) bạn nào thấy hơi khó hiểu thì bản chất là ta đảo ngược vòng for(j) cho chạy từ $sum$ về $1$, bên trong kiểm tra if(!f[j] && j >= a[i]). Vì không còn phải áp dụng công thức $F[i][j] = F[i-1][j]$ nữa (đã bỏ $[i]$), ta đưa luôn điều kiện $j \ge a[i]$ vào điều kiện vòng for: thay vì chạy từ $sum$ về $1$ thì chỉ chạy từ $sum$ về $a[i]$, bên trong chỉ còn kiểm tra if(!f[j]).

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(sum)$. Thực chất là $O(sum + n)$ vì dùng mảng $f$ và mảng $a$, nhưng theo quy tắc Big-O thì là $O(sum)$.
• Thời gian: vẫn là $O(n \cdot sum)$ như cách cũ, nhưng thực tế chạy nhanh hơn (mình đo bản C++ với $n = 100$, $sum$ gần $10^5$ chỉ khoảng 0.03 giây).

Không gian$O(sum)$

Thời gian$O(n \cdot sum)$

Bạn nào code Python để ý

Với $n = 100$, $sum \approx 10^5$ là khoảng $10^7$ phép tính – C++ chạy nhẹ nhàng, nhưng Python thì không: mình đo bản Python của cách 2, 3, 4 lần lượt khoảng 3.9 giây, 3.5 giây và 1.9 giây, đều dễ TLE với giới hạn 1 giây. Nếu muốn nộp Python, các bạn có thể dùng mẹo "mảng bit" bằng số nguyên lớn của Python, ý tưởng y hệt cách 4 (bit thứ $j$ của f bằng 1 nghĩa là tạo được $j$; dịch trái $x$ bit = cộng thêm đồng xu $x$ vào mọi khoản tiền cũ cùng lúc):

f = 1
for x in coins:
    f |= f << x

Bản này mình đo chỉ khoảng 0.3 giây với cùng bộ test lớn.

Ghi chú của mình: code C++ và Python của cả 4 cách đều cho đúng output của ví dụ, và đã được so với code vét cạn (thử mọi tập con đồng xu) trên 400 bộ test ngẫu nhiên nhỏ ($n \le 10$) – khớp hết. Với $n = 100$ và tổng gần $10^5$: bản C++ cách 2 khoảng 0.3 giây (bộ nhớ khoảng 41 MB), cách 3 khoảng 0.07 giây, cách 4 khoảng 0.03 giây; còn cách 1 với $n = 25$ đã chạy quá 60 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇