Bài toán cái túi

Mức độ: Nâng cao

Có n đồ vật, vật thứ i nặng w_i và có giá trị v_i. Cái túi chịu được nhiều nhất W. Chọn các vật để tổng giá trị lớn nhất. Thử mọi cách chọn là 2ⁿ. Khi W không quá lớn (vài trăm nghìn), quy hoạch động theo khối lượng giải trong khoảng n × W bước.

Cái túi 0/1

Mỗi vật chọn hoặc không (0 hoặc 1 lần). Gọi f[i][c] là giá trị lớn nhất khi chỉ xét i vật đầu và túi chịu được c. Với vật thứ i:

• không chọn: f[i - 1][c];
• chọn (nếu w_i ≤ c): f[i - 1][c - w_i] + v_i.

f[i][c] là lớn hơn của hai cách. Ba vật (nặng, giá trị): (1, 1), (3, 4), (4, 5), W = 7:

c	0	1	2	3	4	5	6	7
chưa có vật	0	0	0	0	0	0	0	0
thêm (1, 1)	0	1	1	1	1	1	1	1
thêm (3, 4)	0	1	1	4	5	5	5	5
thêm (4, 5)	0	1	1	4	5	6	6	9

Đáp số 9 (chọn vật 2 và vật 3).

Một mảng, đi ngược. Hàng i chỉ cần hàng i - 1, và ô c chỉ đọc các ô nhỏ hơn hoặc bằng c của hàng trước. Dùng một mảng f và cho c chạy từ W về w_i: khi tính f[c], ô f[c - w_i] chưa bị sửa ở lượt này, vẫn là giá trị của hàng trước. Nhờ vậy mỗi vật chỉ được chọn tối đa một lần.

Python

import sys
du_lieu = sys.stdin.read().split()
n, W = int(du_lieu[0]), int(du_lieu[1])
f = [0] * (W + 1)                    # f[c]: giá trị lớn nhất với túi chịu c
for i in range(n):
    w, v = int(du_lieu[2 + 2 * i]), int(du_lieu[3 + 2 * i])
    for c in range(W, w - 1, -1):    # đi ngược: mỗi vật dùng tối đa một lần
        if f[c - w] + v > f[c]:
            f[c] = f[c - w] + v
print(f[W])

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, W;
    cin >> n >> W;
    vector<long long> f(W + 1, 0);   // f[c]: giá trị lớn nhất với túi chịu c
    for (int i = 0; i < n; i++) {
        int w;
        long long v;
        cin >> w >> v;
        for (int c = W; c >= w; c--) f[c] = max(f[c], f[c - w] + v);   // đi ngược
    }
    cout << f[W] << "\n";
    return 0;
}

Cái túi không giới hạn

Nếu mỗi loại vật lấy được bao nhiêu cũng được, cho c chạy xuôi từ w_i lên W. Khi tính f[c], ô f[c - w_i] đã được cập nhật ở lượt này (có thể đã chứa vật i), nên vật i được dùng thêm lần nữa. Chỉ đổi chiều vòng lặp mà ý nghĩa thay đổi hẳn.

Loại	Chiều của c
mỗi vật tối đa một lần (0/1)	từ W về wi
mỗi vật không giới hạn	từ wi lên W

Có giới hạn số lượng: tách nhị phân

Loại i có k_i cái. Tách thành các “gói” có số lượng 1, 2, 4, …, 2^p và phần còn lại, rồi coi mỗi gói là một vật 0/1. Mọi số lượng từ 0 đến k_i đều ghép được từ các gói (giống biểu diễn nhị phân). Ví dụ k = 13 tách thành 1, 2, 4, 6: số 9 = 1 + 2 + 6, số 13 = 1 + 2 + 4 + 6. Loại có k cái chỉ thành khoảng log₂k vật thay vì k vật.

Các bài cùng khuôn

Bài	Mảng f nghĩa là	Công thức
tổng tập con: đạt được S không	f[c]: đạt được tổng c không	f[c] = f[c] hoặc f[c - ai] (đi ngược)
số cách đổi tiền (không kể thứ tự)	f[c]: số cách tạo c	f[c] += f[c - ai] (đi xuôi, vòng loại tiền ở ngoài)
số tờ ít nhất	f[c]: số tờ ít nhất tạo c	f[c] = min(f[c], f[c - ai] + 1) (đi xuôi)
W rất lớn, giá trị nhỏ	g[v]: khối lượng nhỏ nhất đạt giá trị v	đổi vai khối lượng và giá trị

Luyện tập

Gồm 17 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Ba kiểu cái túi

Bài 1. Cái túi 0/1

Dòng đầu có n, W (1 ≤ n ≤ 100, 0 ≤ W ≤ 10⁵), n dòng sau mỗi dòng có w, v (1 ≤ w ≤ 10⁵, 1 ≤ v ≤ 10⁹) là khối lượng và giá trị một vật. Mỗi vật chọn tối đa một lần, tổng khối lượng không quá W. In ra tổng giá trị lớn nhất.

Ví dụ:

Nhập	In ra
3 7 1 1 3 4 4 5	9

Kiểm tra: nhập

6 15
5 10
4 40
6 30
3 50
7 35
2 15

Xem đáp số

135

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Cái túi không giới hạn

Dòng đầu có n, W (1 ≤ n ≤ 100, 0 ≤ W ≤ 10⁵), n dòng sau mỗi dòng có w, v (1 ≤ w ≤ 10⁵, 1 ≤ v ≤ 10⁹). Mỗi loại vật lấy được bao nhiêu cái cũng được, tổng khối lượng không quá W. In ra tổng giá trị lớn nhất.

Ví dụ:

Nhập	In ra
3 8 2 3 3 5 5 9	14

Kiểm tra: nhập

4 50
7 20
10 31
13 40
17 55

Xem đáp số

157

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Cái túi có giới hạn số lượng

Dòng đầu có n, W (1 ≤ n ≤ 100, 0 ≤ W ≤ 10⁴), n dòng sau mỗi dòng có w, v, k (1 ≤ w ≤ 10⁴, 1 ≤ v ≤ 10⁶, 1 ≤ k ≤ 10⁴): loại thứ i có k cái, mỗi cái nặng w, giá trị v. Tổng khối lượng không quá W. In ra tổng giá trị lớn nhất.

Ví dụ:

Nhập	In ra
3 10 2 3 2 3 5 1 1 2 4	17

Kiểm tra: nhập

4 100
7 20 3
10 31 5
13 40 1
4 11 12

Xem đáp số

299

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Túi phải đầy

Dòng đầu có n, W (1 ≤ n ≤ 100, 0 ≤ W ≤ 10⁵), n dòng sau mỗi dòng có w, v. Chọn mỗi vật tối đa một lần sao cho tổng khối lượng đúng bằng W. In ra tổng giá trị lớn nhất, hoặc -1 nếu không chọn được.

Ví dụ:

Nhập	In ra
3 6 2 3 4 7 5 9	10

Kiểm tra: nhập

5 12
5 10
4 40
6 30
3 50
7 35

Xem đáp số

100

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Tổng tập con

Bài 5. Có tạo được tổng S không

Dòng đầu có n, S (1 ≤ n ≤ 100, 0 ≤ S ≤ 10⁵), dòng thứ hai có n số nguyên dương (a_i ≤ 10⁵). In ra YES nếu chọn được một số phần tử (mỗi phần tử tối đa một lần, có thể không chọn gì) có tổng đúng bằng S, ngược lại NO.

Ví dụ:

Nhập	In ra
5 9 3 34 4 12 5	YES

Kiểm tra: nhập

6 30
7 11 13 2 5 19

Xem đáp số

YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Đếm tập con có tổng S

Dòng đầu có n, S (1 ≤ n ≤ 100, 0 ≤ S ≤ 10⁵), dòng thứ hai có n số nguyên dương (a_i ≤ 10⁵). In ra số tập con (kể cả tập rỗng nếu S = 0; hai tập khác nhau nếu khác vị trí) có tổng đúng bằng S, chia lấy dư 10⁹ + 7.

Ví dụ:

Nhập	In ra
4 5 1 2 3 2	3

Kiểm tra: nhập

8 10
1 2 3 4 5 1 2 3

Xem đáp số

23

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Chia hai phần gần bằng nhau

Dòng đầu có n (1 ≤ n ≤ 100), dòng thứ hai có n số nguyên dương (a_i ≤ 1000). Chia các số thành hai nhóm (nhóm có thể rỗng). In ra chênh lệch nhỏ nhất giữa tổng hai nhóm.

Ví dụ:

Nhập	In ra
4 1 6 11 5	1

Kiểm tra: nhập

8
31 26 33 21 40 25 18 9

Xem đáp số

1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Đặt dấu cộng trừ

Dòng đầu có n, S (1 ≤ n ≤ 100, |S| ≤ 10⁵), dòng thứ hai có n số nguyên dương (a_i ≤ 1000). Đặt dấu + hoặc - trước mỗi số. In ra số cách đặt dấu để tổng bằng S, chia lấy dư 10⁹ + 7.

Ví dụ:

Nhập	In ra
5 3 1 1 1 1 1	5

Kiểm tra: nhập

8 5
2 3 1 4 2 5 1 3

Xem đáp số

20

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Có bao nhiêu tổng khác nhau

Dòng đầu có n (1 ≤ n ≤ 100), dòng thứ hai có n số nguyên dương (a_i ≤ 1000). In ra số giá trị khác nhau mà tổng của một tập con (kể cả tập rỗng, tổng 0) có thể nhận.

Ví dụ:

Nhập	In ra
3 1 2 4	8

Kiểm tra: nhập

6
3 3 5 10 10 20

Xem đáp số

30

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Đổi tiền

Bài 10. Số cách đổi tiền

Có n loại tiền, mệnh giá a₁, …, a_n (khác nhau), mỗi loại có không giới hạn tờ. Dòng đầu có n, S (1 ≤ n ≤ 100, 0 ≤ S ≤ 10⁵), dòng thứ hai có n mệnh giá (1 ≤ a_i ≤ 10⁵). In ra số cách tạo ra đúng S (không kể thứ tự các tờ: 1 + 2 và 2 + 1 là một cách), chia lấy dư 10⁹ + 7.

Ví dụ:

Nhập	In ra
3 5 1 2 5	4

Kiểm tra: nhập

4 30
2 5 3 6

Xem đáp số

52

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Ít tờ tiền nhất

Dòng đầu có n, S (1 ≤ n ≤ 100, 0 ≤ S ≤ 10⁵), dòng thứ hai có n mệnh giá (1 ≤ a_i ≤ 10⁵), mỗi loại không giới hạn tờ. In ra số tờ ít nhất để tạo đúng S, hoặc -1 nếu không được.

Ví dụ:

Nhập	In ra
3 11 1 2 5	3

Kiểm tra: nhập

3 30
1 10 25

Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Leo cầu thang

Cầu thang có S bậc. Mỗi bước được leo a₁, a₂, … hoặc a_n bậc (các số khác nhau). Dòng đầu có n, S (1 ≤ n ≤ 100, 0 ≤ S ≤ 10⁵), dòng thứ hai có n số a_i (1 ≤ a_i ≤ 10⁵). In ra số cách leo đúng S bậc (thứ tự các bước có quan trọng: 1 + 2 và 2 + 1 là hai cách), chia lấy dư 10⁹ + 7.

Ví dụ:

Nhập	In ra
2 4 1 2	5

Kiểm tra: nhập

3 20
1 3 5

Xem đáp số

4285

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Ít tờ nhất, số tờ có hạn

Có n loại tiền, loại thứ i mệnh giá a_i và có k_i tờ. Dòng đầu có n, S (1 ≤ n ≤ 50, 0 ≤ S ≤ 2 × 10⁴), n dòng sau mỗi dòng có a, k (1 ≤ a ≤ 2 × 10⁴, 1 ≤ k ≤ 10⁴). In ra số tờ ít nhất để tạo đúng S, hoặc -1.

Ví dụ:

Nhập	In ra
3 11 5 1 2 3 1 5	4

Kiểm tra: nhập

4 37
10 2
7 3
3 4
1 2

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Biến thể

Bài 14. Túi rất lớn

Dòng đầu có n, W (1 ≤ n ≤ 100, 1 ≤ W ≤ 10⁹), n dòng sau mỗi dòng có w, v (1 ≤ w ≤ 10⁹, 1 ≤ v ≤ 1000). Mỗi vật chọn tối đa một lần, tổng khối lượng không quá W. In ra tổng giá trị lớn nhất.

Ví dụ:

Nhập	In ra
3 8 3 30 4 50 5 60	90

Kiểm tra: nhập

6 1000000000
300000000 70
500000000 120
200000000 40
600000000 160
100000000 15
400000000 110

Xem đáp số

270

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Hai giới hạn: khối lượng và thể tích

Dòng đầu có n, W, V (1 ≤ n ≤ 100, 0 ≤ W, V ≤ 100), n dòng sau mỗi dòng có w, t, v: khối lượng, thể tích, giá trị một vật (1 ≤ w, t ≤ 100, 1 ≤ v ≤ 10⁶). Mỗi vật chọn tối đa một lần, tổng khối lượng không quá W và tổng thể tích không quá V. In ra tổng giá trị lớn nhất.

Ví dụ:

Nhập	In ra
3 5 5 2 3 4 3 2 5 2 2 3	9

Kiểm tra: nhập

5 10 12
4 5 20
3 6 18
5 2 25
2 4 12
6 3 30

Xem đáp số

55

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Mỗi nhóm chọn một

Có g nhóm đồ vật, mỗi nhóm chọn nhiều nhất một vật. Dòng đầu có g, W (1 ≤ g ≤ 100, 0 ≤ W ≤ 10⁴). Tiếp theo là g nhóm: dòng đầu của nhóm có số vật k (1 ≤ k ≤ 100), k dòng sau mỗi dòng có w, v (1 ≤ w ≤ 10⁴, 1 ≤ v ≤ 10⁶). In ra tổng giá trị lớn nhất với tổng khối lượng không quá W.

Ví dụ:

Nhập	In ra
2 7 2 3 5 4 7 2 2 3 5 9	10

Kiểm tra: nhập

3 10
3
2 4
5 9
6 10
2
3 6
7 15
3
1 2
4 7
5 8

Xem đáp số

21

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 17. Chọn đúng k vật

Dòng đầu có n, k, W (1 ≤ k ≤ n ≤ 100, 0 ≤ W ≤ 1000), n dòng sau mỗi dòng có w, v (1 ≤ w ≤ 1000, 1 ≤ v ≤ 10⁶). Chọn đúng k vật khác nhau có tổng khối lượng không quá W. In ra tổng giá trị lớn nhất, hoặc -1 nếu không chọn được.

Ví dụ:

Nhập	In ra
4 2 6 2 3 3 4 4 5 5 6	8

Kiểm tra: nhập

6 3 12
5 10
4 40
6 30
3 50
7 35
2 15

Xem đáp số

105

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.