Cặp Xách

Nguồn: Bài luyện tập Độ khó: Trung bình Quy hoạch động Đệ quy có nhớ Đếm

Đề bài

Cặp Xách

Có $m$ loại đồ dùng học tập với trọng lượng lần lượt là $C_1, C_2, \ldots, C_m$. Số lượng mỗi loại đồ dùng là không giới hạn. Hãy tìm xem có bao nhiêu cách mang theo các đồ dùng học tập sao cho tổng trọng lượng của chúng đúng bằng $n$.

Dữ liệu vào:

• Dòng đầu tiên gồm 2 số nguyên dương $n$, $m$ $(n \le 250;\ m \le 50)$.
• Dòng tiếp theo gồm $m$ số nguyên dương $C_i$ $(1 \le i \le m;\ 1 \le C_i \le 50)$.

Kết quả: in ra số cách tìm được.

(Đề bài được tóm tắt lại từ đề gốc. Hai cách mang được xem là khác nhau khi số lượng của ít nhất một loại đồ dùng khác nhau – thứ tự cho vào cặp không quan trọng.)

Ví dụ – input

4 3
1 2 3

Ví dụ – output

4

Lời mở đầu

Bài này là một biến thể rất hay của bài toán cái túi kinh điển: điểm đặc biệt là mỗi loại đồ dùng được lấy bao nhiêu lần cũng được. Mình sẽ đi theo đúng "lộ trình" quen thuộc: vét cạn bằng đệ quy → đệ quy có nhớ (QHĐ top-down) → QHĐ bottom-up mảng 1 chiều, để các bạn thấy từ một hàm đệ quy ta cải tiến dần như thế nào. Hy vọng mang đến được giá trị cho các bạn 😇.

Bài luyện tập

Bài này hiện chưa có link nộp bài. Các bạn tự kiểm tra bằng cách viết code vét cạn (cách 1 bên dưới chính là một code vét cạn rất tốt), sinh test nhỏ ngẫu nhiên rồi so kết quả với cách tối ưu; hoặc chạy thử code ở trang Chạy code online của blog với test ví dụ nha.

Trước tiên mình tóm tắt lại đề bài cho dễ hiểu: có $m$ loại đồ dùng, loại thứ $i$ nặng $C[i]$, mỗi loại lấy bao nhiêu cái cũng được. Hỏi có bao nhiêu cách chọn để tổng trọng lượng đúng bằng $n$?

Giải thích ví dụ: $n = 4$, $m = 3$, $C = \{1, 2, 3\}$. Có 4 cách mang:

Cách	Các đồ dùng	Tổng
1	1 + 1 + 1 + 1	4
2	1 + 1 + 2	4
3	1 + 3	4
4	2 + 2	4

Để ý $\{1, 3\}$ và $\{3, 1\}$ chỉ là một cách thôi nha (cùng là một cái bút nặng 1 và một cái nặng 3, cho vào cặp trước hay sau đâu có khác gì).

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 · TLECách 2Đệ quy có nhớ · O(n·m)Cách 3QHĐ mảng 1 chiều · O(n·m)

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 thử mọi trường hợp có thể. Bài này rất giống bài toán cái túi kinh điển (bạn nào chưa quen thì có thể đọc thêm bài Money Sum trên blog – mỗi đồng xu ở đó chỉ dùng 1 lần), chỉ khác là ở đây một món chọn bao nhiêu lần cũng được, miễn cặp còn chứa được.

Cách nghĩ dễ bị sai: đếm trùng

Đến đây sẽ có bạn làm thế này: vì mỗi món được chọn không giới hạn, ta viết hàm đệ quy với tham số là trọng lượng cặp còn chứa được; bên trong dùng một vòng for chạy qua tất cả các món đồ xem cho vào cặp được không. Nhưng làm vậy sẽ bị trùng! Ví dụ $n = 4$, $C = \{1, 2, 3\}$: lúc đầu cặp chứa $\{3, 1\}$ → thoả. Về sau lại gặp $\{1, 3\}$ → cũng thoả. Ta đếm thành 2 cách, nhưng thực chất chỉ là 1 cách thôi.

Để xử lý, ta thêm 1 tham số nữa vào hàm đệ quy, tham số này quyết định những món đồ nào còn được cho thêm vào cặp. Nếu đã cho món số 3 vào cặp, về sau cho thêm món số 1 thì được $\{3, 1\}$. Nhưng khi ta đã quyết định chuyển sang món số 1 (tức "không lấy thêm món số 3 nữa") thì sẽ không bao giờ quay lại chọn món số 3, nên không thể sinh ra $\{1, 3\}$ – trường hợp trùng biến mất. Nói cách khác: ta luôn chọn các món theo thứ tự từ món số $m$ lùi dần về món số 1.

Minh hoạ: cách sai (đếm trùng) và cách đúng

Các bạn chọn cách duyệt rồi bấm Tiếp để xem từng cách mang được tìm thấy. Thử nút Ví dụ đề, cách sai trước rồi so với Ví dụ đề, cách đúng nha. Ô đỏ là cách bị đếm trùng:

n Trọng lượng C Cách duyệt (sai / dung)

Ví dụ nhanh:

Xây dựng hàm đệ quy Try(i, j)

Hàm Try(i, j)

Try(i, j) trả về số cách chọn các món trong $i$ món đồ dùng đầu tiên (mỗi món lấy bao nhiêu cái cũng được) cho vào chiếc cặp còn chứa được thêm đúng $j$ trọng lượng.

Điều kiện dừng:

1. Khi chiếc cặp không thể chứa thêm được nữa, tức $j = 0$, thì ta đã hoàn thành được 1 cách chọn, trả về $1$: if(j == 0) return 1;
2. Sau trường hợp trên mà ta không còn món đồ nào để chọn nữa, tức $i = 0$. Đến đây thì chắc chắn $j \ne 0$ (cặp chưa chứa đủ trọng lượng) mà lại hết đồ để xét, nên đây là trường hợp không hợp lệ, trả về $0$: if(i == 0) return 0;

Xử lý chạy: giả sử ta đang xét $i$ món đầu tiên, và đang xét món thứ $i$. Có 2 lựa chọn: không chọn nó (về sau cũng không được chọn nó nữa), hoặc chọn nó (về sau có thể chọn tiếp nó, hoặc thôi không lấy nó nữa). Ta tạo biến res lưu kết quả của Try(i, j).

1Không chọn món thứ $i$: không còn được cho thêm món thứ $i$ vào cặp nữa, nên chỉ còn $i - 1$ món đầu tiên, cặp vẫn còn chứa được $j$. Số cách là Try(i - 1, j). Trường hợp này luôn tồn tại nên khởi tạo luôn res = Try(i - 1, j).

2Chọn món thứ $i$ (khi $C[i] \le j$): cho thêm một món thứ $i$ vào cặp. Vì mỗi loại không giới hạn số lượng nên ta vẫn còn $i$ món để xét, nhưng cặp chỉ còn chứa được $j - C[i]$. Số cách là Try(i, j - C[i]), cộng vào: res += Try(i, j - C[i]).

Công thức

$Try(i, j) = Try(i-1, j) + \big(Try(i, j - C[i])$ nếu $C[i] \le j\big)$, cuối cùng return res;

Điểm khác với cái túi "mỗi món 1 lần"

Ở bài cái túi thường (mỗi món tối đa 1 lần), khi chọn món thứ $i$ thì gọi tiếp Try(i - 1, …) – món $i$ đã dùng rồi. Còn ở bài này gọi Try(i, j - C[i]) – vẫn giữ nguyên $i$ để còn chọn tiếp món đó. Chỉ khác đúng một chữ thôi mà ý nghĩa khác hẳn nha!

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 C[55];

ll Try(int i, int j) {
    if(j == 0) {
        return 1;
    }
    if(i == 0) {
        return 0;
    }
    ll res = Try(i - 1, j);
    if(C[i] <= j) {
        res += Try(i, j - C[i]);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        cin >> C[i];
    }
    cout << Try(m, n);
    return 0;
}

import sys
sys.setrecursionlimit(10000)

def Try(i, j):
    if j == 0:
        return 1
    if i == 0:
        return 0
    res = Try(i - 1, j)
    if C[i] <= j:
        res += Try(i, j - C[i])
    return res

data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
C = [0] + [int(x) for x in data[2:2 + m]]
print(Try(m, n))

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

C++▶ Chạy tay từng dòng codeCách 1: Try(i, j) = Try(i - 1, j) + Try(i, j - C[i]) (nếu C[i] ≤ j).

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

Dữ liệu mẫu:

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

2#define endl '\n'

3

4using namespace std;

5typedef long long ll;

6

7int C[55];

8

9ll Try(int i, int j) {

10 if(j == 0) {

11 return 1;

12 }

13 if(i == 0) {

14 return 0;

15 }

16 ll res = Try(i - 1, j);

17 if(C[i] <= j) {

18 res += Try(i, j - C[i]);

19 }

20 return res;

21}

22

23int main() {

24 ios::sync_with_stdio(0);

25 cin.tie(0);

26 int n, m;

27 cin >> n >> m;

28 for(int i = 1; i <= m; ++i) {

29 cin >> C[i];

30 }

31 cout << Try(m, n);

32 return 0;

33}

ChậmVừaNhanhRất nhanh

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

1. 2 dòng đầu hàm main (ios::sync_with_stdio(0); cin.tie(0);) giúp đẩy nhanh tốc độ nhập xuất dữ liệu khi code C++ (các bạn gõ mấy từ này lên Google là ra rất nhiều bài giải thích nhé). Bài này đầu vào chỉ tầm 50 số nên không cần cũng được, nhưng mình vẫn thêm vì đó là thói quen rồi. Code theo cú pháp C thì chẳng cần mấy dòng đó, nhưng khi code các bài lập trình thi đấu thường ta dùng C++ vì cú pháp ngắn gọn và nhiều hỗ trợ, nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé.
2. ll Try(int i, int j): kiểu trả về của hàm là long long, biến res cũng vậy. Bạn nào để int thì khi cải tiến thành quy hoạch động top-down sẽ bị WA (sai kết quả) do tràn số: với test lớn, số cách chọn rất lớn, hoàn toàn có thể vượt sức chứa của int là $2^{31} - 1 = 2\,147\,483\,647$. Ví dụ $n = 250$, $C = \{1, 2, \ldots, 50\}$ thì đáp án là $189\,335\,266\,912\,037$ – gấp gần 100 nghìn lần giới hạn của int.
3. cout << Try(m, n);: ta cần số cách chọn trong $m$ món đồ đầu tiên ($i = m$) cho chiếc cặp chứa được $n$ ($j = n$).

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

• Thời gian: mỗi lời gọi tách thành tối đa 2 lời gọi con, độ sâu đệ quy tới $n + m$ tầng, nên số lời gọi tăng theo hàm mũ. Mình đo bản C++ với $C = \{1, 2, \ldots, 50\}$: $n = 80$ mất khoảng 0.14 giây, $n = 100$ đã khoảng 1.9 giây, còn $n = 250$ chạy quá 20 giây vẫn chưa xong.
• Không gian: $O(n + m)$ cho mảng $C$ và độ sâu đệ quy.

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

Thời gianHàm mũ

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). Tuy nhiên các bạn vẫn nên cài đặt nó, để làm công cụ kiểm tra tính chính xác cho cách tối ưu, và biết đâu ta có thể cải tiến nó thành quy hoạch động top-down – chính là cách 2 ngay dưới đây.

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

Với code trên ta hoàn toàn có thể cải tiến thành quy hoạch động top-down – đệ quy có nhớ. Nếu đã từng tính Try(i, j) rồi mà lại gặp lại Try(i, j) lần nữa thì theo cách trên ta vẫn phải đi tính lại. Việc tính đi tính lại đó khiến ta tốn rất nhiều thời gian. Giải quyết: dùng một kiểu dữ liệu để lưu kết quả của Try(i, j); đã tính rồi thì trả về kết quả đã lưu, chưa tính thì tính rồi lưu lại để lần sau khỏi tính nữa.

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

2Giới hạn của tham số? $i$ lớn nhất là $m_{max} = 50$, $j$ lớn nhất là $n_{max} = 250$. Khai báo mảng toàn cục long long f[55][255] (mình hay cộng thêm 5).

3Giá trị không thể trả về? Try(i, j) là số cách nên không bao giờ âm, không thể bằng $-1$. Vậy khởi tạo mọi phần tử của $F$ 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[i][j] != -1 thì đã tính rồi, return f[i][j] luôn. Ngược lại tính như bình thường, lưu vào f[i][j] rồi 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 C[55];
ll f[55][255];

ll Try(int i, int j) {
    if(j == 0) {
        return 1;
    }
    if(i == 0) {
        return 0;
    }
    if(f[i][j] != -1) {
        return f[i][j];
    }
    f[i][j] = Try(i - 1, j);
    if(C[i] <= j) {
        f[i][j] += Try(i, j - C[i]);
    }
    return f[i][j];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    fill(&f[1][1], &f[m][n + 1], -1);
    for(int i = 1; i <= m; ++i) {
        cin >> C[i];
    }
    cout << Try(m, n);
    return 0;
}

import sys
sys.setrecursionlimit(10000)

def Try(i, j):
    if j == 0:
        return 1
    if i == 0:
        return 0
    if f[i][j] != -1:
        return f[i][j]
    f[i][j] = Try(i - 1, j)
    if C[i] <= j:
        f[i][j] += Try(i, j - C[i])
    return f[i][j]

data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
C = [0] + [int(x) for x in data[2:2 + m]]
f = [[-1] * (n + 1) for _ in range(m + 1)]
print(Try(m, n))

Trong khung chạy tay dưới đây có thêm bảng $f$ (hàng = $i$, cột = $j$; ô trống là $-1$ – chưa tính). Các bạn để ý những lần ô 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(i, j) vào f[i][j], gặp lại thì trả về luôn.

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

Dữ liệu mẫu:

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

2#define endl '\n'

3

4using namespace std;

5typedef long long ll;

6

7int C[55];

8ll f[55][255];

9

10ll Try(int i, int j) {

11 if(j == 0) {

12 return 1;

13 }

14 if(i == 0) {

15 return 0;

16 }

17 if(f[i][j] != -1) {

18 return f[i][j];

19 }

20 f[i][j] = Try(i - 1, j);

21 if(C[i] <= j) {

22 f[i][j] += Try(i, j - C[i]);

23 }

24 return f[i][j];

25}

26

27int main() {

28 ios::sync_with_stdio(0);

29 cin.tie(0);

30 int n, m;

31 cin >> n >> m;

32 fill(&f[1][1], &f[m][n + 1], -1);

33 for(int i = 1; i <= m; ++i) {

34 cin >> C[i];

35 }

36 cout << Try(m, n);

37 return 0;

38}

ChậmVừaNhanhRất nhanh

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

1. f[i][j] = Try(i - 1, j);: ở đây ta không dùng biến res nữa mà dùng luôn f[i][j] thay vai trò của res.
2. fill(&f[1][1], &f[m][n + 1], -1);: lấp đầy mảng $f$ bằng $-1$. Sau khi qua điều kiện dừng thì $i$ và $j$ đều khác $0$, nên chỉ cần lấp từ $f[1][1]$ tới $f[m][n]$ (mảng 2 chiều nằm liên tiếp trong bộ nhớ, nên fill từ địa chỉ ô $f[1][1]$ tới trước ô $f[m][n+1]$ là phủ hết). Các ô có $i = 0$ hoặc $j = 0$ thì không cần quan tâm vì điều kiện dừng đã lo việc đó rồi.

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

• Không gian: $O(n \cdot m)$ vì dùng mảng $f$. Thực chất là $O(n \cdot m + m)$ vì còn mảng $C$ nữa, nhưng theo quy tắc Big-O thì là $O(n \cdot m)$.
• Thời gian: $O(n \cdot m)$. Trường hợp tệ nhất ta phải lấp đầy mảng $f$, mỗi ô tính một lần trong $O(1)$.

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

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

Vậy với cách trên là ta đã có thể AC bài này rồi (với $n = 250$, $m = 50$ mình đo chưa tới 0.01 giây). Bây giờ mình đến với cách còn tối ưu hơn nữa, tối ưu cả về thời gian lẫn không gian.

Cách 3Phần đọc thêm: QHĐ bottom-up mảng 1 chiều – O(n·m)

Đã có quy hoạch động top-down thì ta cũng có quy hoạch động bottom-up, chính là tạo ra công thức truy hồi. Từ phần top-down ta có ngay:

Công thức truy hồi 2 chiều

$F[i][j] = F[i-1][j]$, và nếu $C[i] \le j$ thì $F[i][j] \mathrel{+}= F[i][j - C[i]]$.

Nhưng cách này không cải tiến quá nhiều, chỉ bớt chút thời gian và bộ nhớ vì không phải gọi đệ quy nữa (ở bài này $n$, $m$ khá bé nên thay đổi không đáng kể). Vậy nên mình sẽ làm cách bottom-up khác chỉ dùng mảng 1 chiều. 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[j]$ là số cách chọn trong $i$ món đồ đầu tiên (vòng for(i) chạy ở ngoài) cho vào chiếc cặp sao cho tổng trọng lượng đúng bằng $j$.

2Bài toán cơ sở: cặp đựng được $0$ thì chỉ có 1 cách là không chọn gì: $F[0] = 1$. Còn $F[1] \ldots F[n] = 0$ (chưa xét món nào mà cần tổng $\gt 0$ thì không có cách nào) – khai báo mảng toàn cục là có sẵn $0$.

3Đáp án: $F[n]$ sau khi đã xét xong cả $m$ món – số cách chọn trong $m$ món đầu tiên để tổng đúng bằng $n$.

4Truy hồi: vòng for(i) từ $1$ tới $m$; bên trong for(j) từ $C[i]$ tới $n$ (cặp phải chứa được ít nhất $C[i]$ thì mới cho món thứ $i$ vào được): $F[j] \mathrel{+}= F[j - C[i]]$.

Giải thích công thức truy hồi: khi xét món thứ $i$, số cách để có tổng $j$ được cộng thêm số cách để có tổng $j - C[i]$, vì chỉ cần thêm một món nặng $C[i]$ vào là cặp có đúng $j$. Trước khi cộng, $F[j]$ đang là số cách không dùng món $i$ (giá trị từ các vòng $i$ trước – ứng với $F[i-1][j]$). Còn $F[j - C[i]]$ đã được cập nhật trong chính vòng $i$ này (vì $j$ chạy tăng dần, $j - C[i] \lt j$ đã xét trước), nên nó là $F[i][j - C[i]]$ – số cách có thể đã dùng món $i$ rồi. Đúng y công thức 2 chiều ở trên!

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

Ở bài cái túi "mỗi món 1 lần" (như bài Money Sum), ta phải duyệt $j$ giảm dần để một món không bị dùng 2 lần. Còn ở bài này mỗi món được dùng không giới hạn, nên duyệt $j$ tăng dần lại chính là điều ta muốn: $F[j - C[i]]$ có thể đã chứa món $i$, cộng thêm một món $i$ nữa là hợp lệ. Còn vòng for(i) nằm ngoài đảm bảo các món luôn được chọn theo thứ tự món 1, rồi món 2, … nên không bị đếm trùng $\{1, 3\}$ với $\{3, 1\}$ (nếu đảo vòng for(j) ra ngoài thì sẽ đếm theo thứ tự – sai giống "cách nghĩ dễ bị sai" ở cách 1).

Minh hoạ: cập nhật mảng F từng ô

Các bạn nhập $n$ và các trọng lượng rồi bấm Tiếp. Ô vàng là $F[j]$ đang cập nhật, ô tím là $F[j - C[i]]$ được cộng vào:

n Trọng lượng C

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 C[55];
ll f[255];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        cin >> C[i];
    }
    f[0] = 1;
    for(int i = 1; i <= m; ++i) {
        for(int j = C[i]; j <= n; ++j) {
            f[j] += f[j - C[i]];
        }
    }
    cout << f[n];
    return 0;
}

data = open(0).read().split()
n, m = int(data[0]), int(data[1])
C = [0] + [int(x) for x in data[2:2 + m]]
f = [0] * (n + 1)
f[0] = 1
for i in range(1, m + 1):
    for j in range(C[i], n + 1):
        f[j] += f[j - C[i]]
print(f[n])

C++▶ Chạy tay từng dòng codeCách 3: f[0] = 1; với mỗi món i, duyệt j tăng từ C[i] tới n: f[j] += f[j - C[i]].

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

Dữ liệu mẫu:

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

2#define endl '\n'

3

4using namespace std;

5typedef long long ll;

6

7int C[55];

8ll f[255];

9

10int main() {

11 ios::sync_with_stdio(0);

12 cin.tie(0);

13 int n, m;

14 cin >> n >> m;

15 for(int i = 1; i <= m; ++i) {

16 cin >> C[i];

17 }

18 f[0] = 1;

19 for(int i = 1; i <= m; ++i) {

20 for(int j = C[i]; j <= n; ++j) {

21 f[j] += f[j - C[i]];

22 }

23 }

24 cout << f[n];

25 return 0;

26}

ChậmVừaNhanhRất nhanh

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

• Không gian: $O(n + m)$, vì giờ chỉ còn mảng $f$ và mảng $C$. Bạn nào muốn thì có thể bỏ luôn mảng $C$, vừa đọc đầu vào vừa xử lý luôn cũng được nha.
• Thời gian: $O(n \cdot m)$. Tuy độ phức tạp giống cách trên nhưng thực tế code chạy nhanh hơn và ăn ít bộ nhớ hơn. Do ở đây $n$ và $m$ quá bé nên sự chênh lệch giữa 2 cách là không lớn (đều chưa tới 0.01 giây).

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

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

Lưu ý nhỏ về tràn số

Mình đã thử trường hợp đáp án lớn nhất khi các trọng lượng khác nhau: $n = 250$, $C = \{1, 2, \ldots, 50\}$ cho $189\,335\,266\,912\,037 \approx 1.9 \cdot 10^{14}$, long long chứa thoải mái. Nhưng nếu đề cho phép nhiều loại đồ dùng trùng trọng lượng (ví dụ cả 50 loại đều nặng 1, mỗi loại tính là khác nhau) thì đáp án lên tới cỡ $10^{56}$, vượt cả long long – khi đó đề thường sẽ yêu cầu in kết quả chia lấy dư cho một số nào đó. Bản Python thì không lo chuyện này vì số nguyên của Python không giới hạn.

Ghi chú của mình: code C++ và Python của cả 3 cách đều cho đúng output của ví dụ, và đã được so với một code vét cạn khác (thử mọi số lượng của từng loại) trên 400 bộ test ngẫu nhiên nhỏ ($n \le 22$, $m \le 6$, có cả trọng lượng trùng nhau) – khớp hết. Với $n = 250$, $m = 50$: cách 2 và cách 3 (C++ lẫn Python) đều chạy dưới 0.03 giây và cho cùng đáp án; cách 1 với $n = 100$ đã mất khoảng 1.9 giây, $n = 250$ chạy quá 20 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 😇