Quy hoạch động (3): cái túi
- Độ khó
- ★★★★★ Khó
- Thời lượng
- Khoảng 120 phút
- Học trước
- Quy hoạch động (2)
- Chủ đề
- knapsackquy hoạch động
- Trạng thái
Kiến thức cơ bản
Nhìn lại quy hoạch động
Ở hai tuần trước, em đã biết quy hoạch động (DP) là cách giải một bài lớn bằng cách ghi nhớ đáp án của các bài nhỏ hơn. Mỗi bài DP em luôn phải trả lời ba câu hỏi: trạng thái là gì (dp[...] nghĩa là gì), công thức nối các trạng thái với nhau ra sao, và trường hợp cơ sở (trạng thái bé nhất, biết ngay đáp án) là gì.
Tuần này, ta gặp bài DP nổi tiếng nhất: bài cái túi (knapsack). Đây là tuần khó, em nên học làm hai buổi. Buổi 1: Mẫu 1, 2 và các bài luyện tập 1, 2. Buổi 2: Mẫu 3 đến Mẫu 5 và các bài còn lại.
Mẫu 1: Bài toán cái túi
Gấu Po chuẩn bị đi dã ngoại. Ba lô của Gấu Po chứa được tối đa W ki-lô-gam. Có n món đồ, món thứ i nặng w[i] ki-lô-gam và được Gấu Po chấm v[i] điểm yêu thích. Mỗi món chỉ có một chiếc: với mỗi món, Gấu Po chỉ có hai lựa chọn là lấy hoặc không lấy. Hỏi tổng điểm yêu thích lớn nhất mang đi được là bao nhiêu?
Em có thể nghĩ ngay đến hai cách quen thuộc. Cách thứ nhất là thử mọi cách chọn: n món có 2n cách, với n = 40 đã là hơn 1012 cách, quá chậm. Cách thứ hai là tham lam, nhưng tham lam ở bài này có thể sai. Ví dụ sau cho thấy điều đó.
Sức chứa ba lô: W = 5 kg
Món A: nặng 3, thích 4 (được 1,33 điểm mỗi kg)
Món B: nặng 2, thích 3 (được 1,5 điểm mỗi kg)
Món C: nặng 2, thích 3 (được 1,5 điểm mỗi kg)
Tham lam theo "điểm mỗi kg": lấy B và C -> nặng 4, được 6 điểm,
còn 1 kg trống nhưng A không vừa. KẾT QUẢ 6.
Cách tốt nhất: lấy A và B -> nặng 5, được 7 điểm. KẾT QUẢ 7.
Vậy ta cần một cách khác: lập bảng DP để cân nhắc mọi khả năng mà không phải thử từng cách một.
Mẫu 2: Bảng DP hai chiều
Trạng thái: dp[i][j] là tổng điểm lớn nhất khi chỉ được chọn trong i món đầu tiên và ba lô chứa tối đa j ki-lô-gam.
Công thức: xét món thứ i. Có hai lựa chọn. Nếu không lấy món i, điểm là dp[i-1][j]. Nếu lấy món i (chỉ làm được khi j ≥ w[i]), em dành w[i] ki-lô-gam cho nó, phần còn lại dùng tốt nhất cho i-1 món đầu, điểm là dp[i-1][j-w[i]] + v[i]. Lấy cách nào tốt hơn:
dp[i][j] = max( dp[i-1][j] , dp[i-1][j - w[i]] + v[i] )
(bỏ món i) (lấy món i, chỉ khi j >= w[i])
Trường hợp cơ sở: dp[0][j] = 0, vì chưa có món nào thì chưa có điểm nào. Đáp án của bài là dp[n][W]. Với ví dụ ở Mẫu 1, em điền bảng từng hàng từ trên xuống:
j = 0 1 2 3 4 5
(chưa có món) 0 0 0 0 0 0
i = 1 (món A) 0 0 0 4 4 4
i = 2 (món B) 0 0 3 4 4 7
i = 3 (món C) 0 0 3 4 6 7
Đáp án: dp[3][5] = 7
Ví dụ ô dp[2][5] = 7: không lấy B thì được dp[1][5] = 4; lấy B (nặng 2) thì còn 3 kg cho món A, được dp[1][3] + 3 = 4 + 3 = 7. Cách thứ hai tốt hơn nên ghi 7.
- Lưu ý: Các đoạn code trong bài này chỉ là phần thân của hàm main. Em nhớ thêm #include <bits/stdc++.h> và using namespace std; khi chạy thật.
int n, W;
cin >> n >> W;
vector<int> w(n + 1);
vector<long long> v(n + 1);
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
vector<vector<long long>> dp(n + 1, vector<long long>(W + 1, 0)); // dp[0][j] = 0
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= W; j++) {
dp[i][j] = dp[i - 1][j]; // không lấy món i
if (j >= w[i]) // ba lô còn đủ chỗ cho món i
dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]); // lấy món i
}
}
cout << dp[n][W] << endl;
Bảng có (n + 1) × (W + 1) ô, mỗi ô tính trong một bước, nên cả bài mất khoảng n × W phép tính. Với n = 100 và W = 104 thì chỉ khoảng một triệu phép tính, máy tính chạy trong một cái chớp mắt.
Ba chỗ em hay viết sai:
- Mảng dp phải có W + 1 cột (chỉ số từ 0 đến W), nếu chỉ khai báo W cột thì ô dp[i][W] nằm ngoài mảng.
- Phải kiểm tra j >= w[i] trước khi viết dp[i-1][j - w[i]]. Nếu thiếu, chỉ số có thể âm và chương trình chạy sai.
- Điểm cộng dồn có thể lên tới 100 × 109 = 1011, vượt quá int. Dùng long long cho v và dp.
Mẫu 3: Thu gọn thành một hàng
Nhìn lại công thức, hàng i chỉ cần hàng i-1. Vậy em không cần giữ cả bảng, chỉ cần một hàng dp[j], rồi cập nhật hàng đó qua từng món. Lúc này dp[j] là tổng điểm lớn nhất khi ba lô chứa tối đa j ki-lô-gam, với các món đã xét.
Điều quan trọng nhất của mẫu này: vòng for theo j phải chạy ngược, từ W xuống w. Lý do: khi tính dp[j] cần giá trị dp[j - w] của hàng cũ (chưa xét món hiện tại). Nếu chạy xuôi, ô dp[j - w] đã bị cập nhật bởi chính món này, và món ấy bị lấy hai lần. Hãy xem món B (nặng 2, điểm 3) được thêm vào hàng sau khi đã có món A:
Hàng đang có (sau món A): j = 0 1 2 3 4 5
dp = 0 0 0 4 4 4
Chạy NGƯỢC (j = 5, 4, 3, 2): dp[5] = max(4, dp[3] + 3) = 7
dp[4] = max(4, dp[2] + 3) = 4
dp[3] = max(4, dp[1] + 3) = 4
dp[2] = max(0, dp[0] + 3) = 3
--> dp = 0 0 3 4 4 7 ĐÚNG
Chạy XUÔI (j = 2, 3, 4, 5): dp[2] = 3
dp[4] = max(4, dp[2] + 3) = 6 (dp[2] đã có B rồi!)
--> dp[4] = 6: món B bị lấy hai lần SAI
int n, W;
cin >> n >> W;
vector<long long> dp(W + 1, 0); // dp[j] = điểm lớn nhất khi ba lô chứa tối đa j kg
for (int i = 1; i <= n; i++) {
int w;
long long v;
cin >> w >> v;
for (int j = W; j >= w; j--) // chạy NGƯỢC từ W xuống w
dp[j] = max(dp[j], dp[j - w] + v);
}
cout << dp[W] << endl;
Cách này chạy cùng số phép tính nhưng chỉ cần một mảng W + 1 phần tử. Nếu w lớn hơn W thì vòng for không chạy lần nào, nghĩa là bỏ qua món quá nặng, đúng như mong muốn.
Mẫu 4: Ba biến thể hay gặp
Khung "chạy ngược trên mảng dp" dùng được cho rất nhiều bài, chỉ cần đổi ý nghĩa của dp[j] và cách khởi tạo.
Biến thể 1: tạo được tổng S hay không? Cho n số, hỏi có chọn được vài số (mỗi số dùng tối đa một lần) có tổng đúng S không? Ở đây dp[j] chỉ là đúng hoặc sai.
int n, S;
cin >> n >> S;
vector<bool> dp(S + 1, false); // dp[j] = có tạo được tổng j không?
dp[0] = true; // không chọn gì thì tổng bằng 0
for (int i = 0; i < n; i++) {
int a;
cin >> a;
for (int j = S; j >= a; j--)
if (dp[j - a]) dp[j] = true;
}
cout << (dp[S] ? "YES" : "NO") << endl;
Biến thể 2: đếm số cách. Chỉ cần đổi "có thể" thành "số cách". Hai cách chọn ra cùng một tổng thì cộng lại với nhau. Số cách rất lớn nên đề thường yêu cầu lấy phần dư khi chia cho 109 + 7.
const long long MOD = 1000000007;
vector<long long> dp(S + 1, 0); // dp[j] = số cách chọn ra tổng j
dp[0] = 1; // một cách: không chọn gì
for (int i = 0; i < n; i++) {
int a;
cin >> a;
for (int j = S; j >= a; j--)
dp[j] = (dp[j] + dp[j - a]) % MOD;
}
Biến thể 3: ba lô phải đầy đúng W. Ở bài gốc, dp khởi tạo 0 nghĩa là ba lô được phép còn trống. Nếu đề bắt buộc tổng cân nặng đúng bằng W, ta khởi tạo dp[0] = 0 còn các ô khác là -1 (nghĩa là chưa làm đầy được), và chỉ nối tiếp từ ô đã làm được.
vector<long long> dp(W + 1, -1); // -1 nghĩa là "không thể làm đầy đúng j kg"
dp[0] = 0;
for (int i = 1; i <= n; i++)
for (int j = W; j >= w[i]; j--)
if (dp[j - w[i]] != -1) // chỉ nối tiếp từ trạng thái đã làm được
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout << dp[W] << endl; // in -1 nếu không thể làm đầy
Mẫu 5: Mỗi loại lấy bao nhiêu cũng được (đổi xu)
Nếu mỗi loại đồ có rất nhiều chiếc (như đồng xu), mỗi loại được dùng nhiều lần. Bài đổi xu: có các loại xu mệnh giá c[i], hỏi cần ít nhất bao nhiêu xu để trả đúng S đồng. Tuần 29 em đã thấy tham lam có thể sai ở bài này: với xu 1, 3, 4 và S = 6, tham lam lấy 4 + 1 + 1 (3 xu) nhưng 3 + 3 chỉ cần 2 xu.
Cách nghĩ giống bài leo cầu thang ở tuần 30: để trả j đồng, đồng xu cuối cùng có thể là loại c nào đó, khi đó phần còn lại là j - c đồng. Vậy dp[j] = min của dp[j - c] + 1 trên mọi loại xu c (với c ≤ j). Trường hợp cơ sở: dp[0] = 0, các ô chưa làm được là INF (một số rất lớn).
int n, S;
cin >> n >> S;
vector<int> coin(n);
for (int &c : coin) cin >> c;
const int INF = 1000000000;
vector<int> dp(S + 1, INF); // dp[j] = số xu ít nhất để trả đúng j đồng
dp[0] = 0;
for (int j = 1; j <= S; j++)
for (int c : coin) // thử từng loại xu làm đồng xu cuối cùng
if (j >= c && dp[j - c] != INF)
dp[j] = min(dp[j], dp[j - c] + 1);
cout << (dp[S] == INF ? -1 : dp[S]) << endl;
Đoạn code này tốn khoảng S × n phép tính. Với S = 105 và n = 50 thì khoảng 5 triệu phép tính, rất nhanh.
Cẩn thận với hai bài rất giống nhau: "đếm số dãy bước" (1 + 2 và 2 + 1 là hai cách) và "đếm số cách trả tiền" (1 + 2 và 2 + 1 là một cách). Hai bài này cần hai vòng for lồng nhau theo hai thứ tự khác nhau. Em hãy thử bằng tay với xu {1, 2} và S = 3: có 2 cách hay 3 cách? Rồi tự tìm ra thứ tự vòng for đúng cho từng bài ở phần luyện tập và tự luyện.
Mở rộng (không bắt buộc): tìm xem đã lấy những món nào
Đôi khi đề không chỉ hỏi điểm lớn nhất mà còn hỏi đã lấy những món nào. Khi đó em giữ bảng hai chiều dp[i][j] và đi ngược từ ô dp[n][W]: nếu dp[i][j] khác dp[i-1][j] thì món i đã được lấy (vì nếu không lấy thì hai giá trị phải bằng nhau), rồi trừ w[i] khỏi j. Với ví dụ ở Mẫu 2, đoạn code sau in ra "2 1", nghĩa là lấy món B và món A.
int j = W;
for (int i = n; i >= 1; i--) {
if (dp[i][j] != dp[i - 1][j]) { // giá trị đổi nghĩa là món i đã được lấy
cout << i << " ";
j -= w[i]; // trả lại chỗ trong ba lô
}
}
Nhận dạng đề bài
| Dấu hiệu trong đề | Công cụ | Cách làm |
|---|---|---|
| Mỗi món lấy hoặc không (tối đa một lần), có giới hạn cân nặng, hỏi giá trị lớn nhất | Túi 0/1 | dp[j], vòng j chạy ngược từ W xuống w |
| Chọn một số phần tử để tổng đúng S: có được không? | Túi dạng đúng/sai | dp[0] = true, chạy ngược |
| Đếm số cách chọn ra tổng S | Túi đếm cách | dp[0] = 1, dp[j] += dp[j - a], nhớ lấy phần dư |
| Mỗi loại dùng nhiều lần, ít xu nhất hoặc nhiều xu nhất | Túi không giới hạn | dp[j] = min (hoặc max) của dp[j - c] + 1 |
| Tổng cân nặng phải đúng bằng W | Túi phải đầy | Ô chưa làm được đặt là -1, chỉ nối tiếp từ ô đã làm được |
| W hoặc w[i] lên tới hàng tỷ nhưng n ≤ 20 | Không dùng DP | Thử mọi tập con 2n (vét cạn hoặc quay lui) |
| W hoặc w[i] rất lớn nhưng tổng điểm nhỏ | Đổi vai trạng thái | dp[điểm] = cân nặng nhỏ nhất để đạt điểm đó |
Luyện tập
Bài 1. Ba lô dã ngoại
Gấu Po chuẩn bị đi dã ngoại. Ba lô của Gấu Po chứa được tối đa W ki-lô-gam. Gấu Po có n món đồ, món thứ i nặng w[i] ki-lô-gam và được Gấu Po chấm v[i] điểm yêu thích. Mỗi món chỉ có một chiếc. Hãy chọn các món sao cho tổng cân nặng không vượt quá W và tổng điểm yêu thích lớn nhất. (Gợi ý: dùng bảng dp hai chiều như Mẫu 2.)
| Đầu vào | Dòng 1: hai số nguyên n, W (1 ≤ n ≤ 100, 1 ≤ W ≤ 104). n dòng tiếp theo: dòng thứ i gồm hai số nguyên w[i], v[i] (1 ≤ w[i] ≤ 104, 1 ≤ v[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng điểm yêu thích lớn nhất có thể. | |
| Test | Input | Output |
| 1 | 4 7 3 4 4 5 2 3 5 7 | 10 |
| 2 | 3 5 6 100 2 3 3 4 | 7 |
Bài 2. Chọn cỡ ba lô
Hổ đi mua ba lô cho Gấu Po. Cửa hàng có các cỡ chứa được 1, 2, ..., W ki-lô-gam. Gấu Po có n món đồ như bài trước (mỗi món chỉ có một chiếc). Với mỗi cỡ ba lô j từ 1 đến W, hãy cho biết tổng điểm yêu thích lớn nhất khi dùng cỡ đó, để Hổ chọn được cỡ vừa túi tiền.
| Đầu vào | Dòng 1: hai số nguyên n, W (1 ≤ n ≤ 100, 1 ≤ W ≤ 103). n dòng tiếp theo: dòng thứ i gồm hai số nguyên w[i], v[i] (1 ≤ w[i] ≤ 103, 1 ≤ v[i] ≤ 109). | |
|---|---|---|
| Đầu ra | W số nguyên trên một dòng, số thứ j là tổng điểm lớn nhất với ba lô cỡ j. | |
| Test | Input | Output |
| 1 | 3 5 3 4 2 3 2 3 | 0 3 4 6 7 |
| 2 | 2 4 5 10 1 2 | 2 2 2 2 |
Bài 3. Tiệc bánh vừa đủ
Thỏ có n chiếc bánh, chiếc thứ i nặng a[i] gam. Thỏ muốn chọn một số chiếc bánh (mỗi chiếc dùng tối đa một lần) sao cho tổng khối lượng đúng bằng S gam để bày vừa khít một chiếc đĩa. Hỏi Thỏ có làm được không?
| Đầu vào | Dòng 1: hai số nguyên n, S (1 ≤ n ≤ 100, 1 ≤ S ≤ 104). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 104). | |
|---|---|---|
| Đầu ra | In YES nếu làm được, ngược lại in NO. | |
| Test | Input | Output |
| 1 | 5 9 3 34 4 12 5 | YES |
| 2 | 4 11 2 4 6 8 | NO |
Bài 4. Chọn quà đúng giá
Gấu Po có n món quà, món thứ i có giá a[i] đồng. Gấu Po muốn chọn ra một số món có tổng giá đúng S đồng để tặng bạn. Hai cách chọn được coi là khác nhau nếu có một món được chọn ở cách này mà không được chọn ở cách kia (hai món cùng giá nhưng là hai món khác nhau thì vẫn tính là khác nhau). Hãy đếm số cách chọn, lấy phần dư khi chia cho 109 + 7.
| Đầu vào | Dòng 1: hai số nguyên n, S (1 ≤ n ≤ 100, 1 ≤ S ≤ 104). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Số cách chọn, lấy phần dư khi chia cho 109 + 7. | |
| Test | Input | Output |
| 1 | 4 5 1 2 3 4 | 2 |
| 2 | 5 5 1 1 1 1 1 | 1 |
Bài 5. Chia đôi kho báu
Gấu Po và Thỏ tìm được n viên ngọc, viên thứ i có giá trị a[i]. Hai bạn muốn chia hết các viên ngọc, mỗi viên thuộc về đúng một bạn, sao cho chênh lệch giữa tổng giá trị của hai bạn là nhỏ nhất. Hãy tìm chênh lệch nhỏ nhất đó. (Gợi ý: nếu một bạn nhận tổng j thì bạn kia nhận tổng T - j, với T là tổng tất cả.)
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 100). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 100). | |
|---|---|---|
| Đầu ra | Chênh lệch nhỏ nhất. | |
| Test | Input | Output |
| 1 | 4 1 6 11 5 | 1 |
| 2 | 3 7 7 7 | 7 |
Bài 6. Đổi xu ít nhất
Hổ có n loại xu, loại thứ i có mệnh giá c[i] đồng và mỗi loại có rất nhiều đồng. Hổ cần trả đúng S đồng bằng ít đồng xu nhất. Hãy cho biết số xu ít nhất, hoặc in -1 nếu không thể trả đúng S đồng. (Với các loại xu 1, 3, 4 và S = 6, cách tham lam 4 + 1 + 1 dùng 3 xu, nhưng cách tốt nhất là 3 + 3 chỉ dùng 2 xu.)
| Đầu vào | Dòng 1: hai số nguyên n, S (1 ≤ n ≤ 50, 1 ≤ S ≤ 105). Dòng 2: n số nguyên đôi một khác nhau c[i] (1 ≤ c[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Số xu ít nhất, hoặc -1 nếu không thể. | |
| Test | Input | Output |
| 1 | 3 6 1 3 4 | 2 |
| 2 | 2 7 2 4 | -1 |
Bài 7. Ba lô phải đầy
Thỏ thích ba lô căng đầy. Ba lô chứa đúng W ki-lô-gam, Thỏ có n món đồ (món thứ i nặng w[i], được v[i] điểm yêu thích, mỗi món một chiếc) và muốn tổng cân nặng các món mang theo đúng bằng W, không thiếu không thừa. Trong các cách làm đầy ba lô, hãy tìm tổng điểm lớn nhất, hoặc in -1 nếu không có cách nào làm đầy đúng W.
| Đầu vào | Dòng 1: hai số nguyên n, W (1 ≤ n ≤ 100, 1 ≤ W ≤ 104). n dòng tiếp theo: dòng thứ i gồm hai số nguyên w[i], v[i] (1 ≤ w[i] ≤ 104, 1 ≤ v[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng điểm lớn nhất, hoặc -1 nếu không thể. | |
| Test | Input | Output |
| 1 | 3 5 2 3 3 4 4 6 | 7 |
| 2 | 2 4 3 5 5 9 | -1 |
Bài 8. Chợ trái cây
Gấu Po đi chợ mua trái cây về ăn dọc đường. Chợ có n loại trái cây, mỗi quả loại thứ i nặng w[i] ki-lô-gam, được Gấu Po chấm v[i] điểm, và chợ còn đúng k[i] quả loại đó. Ba lô chứa tối đa W ki-lô-gam. Hãy chọn số quả mỗi loại để tổng điểm lớn nhất. (Gợi ý: coi k[i] quả giống nhau như k[i] món riêng biệt.)
| Đầu vào | Dòng 1: hai số nguyên n, W (1 ≤ n ≤ 100, 1 ≤ W ≤ 103). n dòng tiếp theo: dòng thứ i gồm ba số nguyên w[i], v[i], k[i] (1 ≤ w[i] ≤ 103, 1 ≤ v[i] ≤ 109, 1 ≤ k[i] ≤ 10). | |
|---|---|---|
| Đầu ra | Tổng điểm lớn nhất. | |
| Test | Input | Output |
| 1 | 2 10 3 4 2 5 7 3 | 14 |
| 2 | 2 6 4 10 1 2 3 5 | 13 |
Bài 9. Số cách trả tiền
Hổ có n loại xu, loại thứ i có mệnh giá c[i] đồng và mỗi loại có rất nhiều đồng. Hãy đếm số cách trả đúng S đồng. Hai cách được coi là giống nhau nếu dùng cùng số lượng xu của mỗi loại, không quan tâm thứ tự đưa xu (ví dụ 1 + 2 và 2 + 1 chỉ là một cách). Lấy phần dư khi chia cho 109 + 7.
| Đầu vào | Dòng 1: hai số nguyên n, S (1 ≤ n ≤ 50, 1 ≤ S ≤ 104). Dòng 2: n số nguyên đôi một khác nhau c[i] (1 ≤ c[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Số cách trả, lấy phần dư khi chia cho 109 + 7. | |
| Test | Input | Output |
| 1 | 3 4 1 2 3 | 4 |
| 2 | 3 10 2 5 10 | 3 |
Bài tập tự luyện
Bài 1. Kho báu trên đảo
Gấu Po tìm thấy n món kho báu trên một hòn đảo. Món thứ i nặng w[i] và có giá trị v[i]. Chiếc thuyền của Gấu Po chở được tối đa W ki-lô-gam. Mỗi món chỉ có một chiếc. Hãy tìm tổng giá trị lớn nhất mà thuyền chở được. (Chú ý cách nhập: dòng 2 là các cân nặng, dòng 3 là các giá trị.)
| Đầu vào | Dòng 1: hai số nguyên n, W (1 ≤ n ≤ 100, 1 ≤ W ≤ 104). Dòng 2: n số nguyên w[i] (1 ≤ w[i] ≤ 104). Dòng 3: n số nguyên v[i] (1 ≤ v[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng giá trị lớn nhất. | |
| Test | Input | Output |
| 1 | 4 8 5 4 6 3 10 40 30 50 | 90 |
| 2 | 3 3 4 5 6 10 20 30 | 0 |
Bài 2. Những tổng có thể
Thỏ có n quả cân, quả thứ i nặng a[i] gam. Thỏ chọn một số quả cân (ít nhất một quả) đặt lên một đĩa cân. Hổ hỏi: có bao nhiêu số gam khác nhau mà Thỏ có thể cân được?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 100). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 100). | |
|---|---|---|
| Đầu ra | Số lượng tổng khối lượng khác nhau (tính các tổng ≥ 1). | |
| Test | Input | Output |
| 1 | 3 1 2 4 | 7 |
| 2 | 4 3 3 3 3 | 4 |
Bài 3. Nhiều xu nhất
Gấu Po muốn khoe túi tiền nặng trĩu nên cần trả đúng S đồng bằng NHIỀU đồng xu nhất có thể. Có n loại xu, mỗi loại có rất nhiều đồng. Hãy cho biết số xu nhiều nhất, hoặc in -1 nếu không thể trả đúng S đồng.
| Đầu vào | Dòng 1: hai số nguyên n, S (1 ≤ n ≤ 50, 1 ≤ S ≤ 105). Dòng 2: n số nguyên đôi một khác nhau c[i] (1 ≤ c[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Số xu nhiều nhất, hoặc -1 nếu không thể. | |
| Test | Input | Output |
| 1 | 3 10 2 3 5 | 5 |
| 2 | 2 7 4 6 | -1 |
Bài 4. Chọn không vượt quá
Hổ có n viên đá, viên thứ i nặng w[i]. Hổ muốn chọn ra một số viên (có thể không chọn viên nào) sao cho tổng cân nặng không vượt quá W. Hãy đếm số cách chọn, lấy phần dư khi chia cho 109 + 7.
| Đầu vào | Dòng 1: hai số nguyên n, W (1 ≤ n ≤ 100, 1 ≤ W ≤ 104). Dòng 2: n số nguyên w[i] (1 ≤ w[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Số cách chọn, lấy phần dư khi chia cho 109 + 7. | |
| Test | Input | Output |
| 1 | 3 4 1 2 3 | 6 |
| 2 | 4 5 2 2 2 2 | 11 |
Bài 5. Nhiều nhất k món
Gấu Po đi chơi nhưng chỉ nhớ mang được tối đa k món đồ. Ba lô chứa được tối đa W ki-lô-gam. Có n món, món thứ i nặng w[i] và có v[i] điểm yêu thích. Hãy chọn không quá k món, tổng cân nặng không vượt quá W, sao cho tổng điểm lớn nhất. (Gợi ý: trạng thái cần thêm một chiều để đếm số món đã chọn.)
| Đầu vào | Dòng 1: ba số nguyên n, k, W (1 ≤ k ≤ n ≤ 50, 1 ≤ W ≤ 500). n dòng tiếp theo: dòng thứ i gồm hai số nguyên w[i], v[i] (1 ≤ w[i] ≤ 500, 1 ≤ v[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng điểm lớn nhất. | |
| Test | Input | Output |
| 1 | 4 2 10 5 10 4 40 6 30 3 50 | 90 |
| 2 | 3 1 5 2 3 3 5 4 4 | 5 |
Bài 6. Ba lô khổng lồ
Thỏ có chiếc ba lô khổng lồ, chứa bao nhiêu cũng được. Thỏ có n món đồ, món thứ i nặng w[i] và có v[i] điểm yêu thích. Thỏ muốn tổng điểm đạt ít nhất K nhưng muốn ba lô nhẹ nhất có thể. Hãy tìm tổng cân nặng nhỏ nhất, hoặc in -1 nếu dù lấy hết vẫn không đạt K điểm. (Gợi ý: cân nặng rất lớn, nhưng điểm thì nhỏ. Hãy đổi vai: lấy điểm làm chỉ số của mảng dp.)
| Đầu vào | Dòng 1: hai số nguyên n, K (1 ≤ n ≤ 100, 1 ≤ K ≤ 104). n dòng tiếp theo: dòng thứ i gồm hai số nguyên w[i], v[i] (1 ≤ w[i] ≤ 109, 1 ≤ v[i] ≤ 100). | |
|---|---|---|
| Đầu ra | Tổng cân nặng nhỏ nhất, hoặc -1 nếu không thể. | |
| Test | Input | Output |
| 1 | 3 7 10 3 20 5 35 4 | 30 |
| 2 | 2 20 5 4 7 6 | -1 |
Bài 7. Những bước nhảy của Thỏ
Thỏ muốn nhảy từ mặt đất lên bậc thang thứ S. Mỗi bước, Thỏ nhảy được đúng một độ dài thuộc n độ dài cho trước (độ dài nào cũng dùng được nhiều lần). Hai dãy bước có cùng các độ dài nhưng thứ tự khác nhau được coi là hai cách khác nhau (1 + 2 và 2 + 1 là hai cách). Hãy đếm số cách nhảy đúng tới bậc S, lấy phần dư khi chia cho 109 + 7. (So sánh với bài Số cách trả tiền ở phần luyện tập: hai bài khác nhau ở chỗ nào?)
| Đầu vào | Dòng 1: hai số nguyên n, S (1 ≤ n ≤ 50, 1 ≤ S ≤ 105). Dòng 2: n số nguyên đôi một khác nhau c[i] (1 ≤ c[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Số cách nhảy, lấy phần dư khi chia cho 109 + 7. | |
| Test | Input | Output |
| 1 | 2 4 1 2 | 5 |
| 2 | 3 10 1 3 4 | 64 |
Bài 8. Món đồ nặng như núi
Hổ có n món đồ rất to, món thứ i nặng w[i] và có v[i] điểm. Chiếc xe của Hổ chở được tối đa W. Lần này n rất nhỏ nhưng W và w[i] lên tới hàng tỷ nên không thể lập mảng dp theo cân nặng. Hãy tìm tổng điểm lớn nhất. (Gợi ý: với n nhỏ, em có cách nào thử hết mọi cách chọn?)
| Đầu vào | Dòng 1: hai số nguyên n, W (1 ≤ n ≤ 20, 1 ≤ W ≤ 109). n dòng tiếp theo: dòng thứ i gồm hai số nguyên w[i], v[i] (1 ≤ w[i], v[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng điểm lớn nhất (có thể vượt quá giới hạn của int). | |
| Test | Input | Output |
| 1 | 4 10 6 60 5 50 4 70 3 30 | 130 |
| 2 | 3 100 60 5 50 6 40 7 | 13 |
Bài 9. Ba lô hai ràng buộc (không bắt buộc)
Gấu Po đóng gói đồ cho chuyến đi. Ba lô chịu được tối đa A ki-lô-gam và chứa được tối đa B lít. Món thứ i nặng a[i] ki-lô-gam, chiếm b[i] lít và có v[i] điểm yêu thích. Mỗi món chỉ có một chiếc. Hãy chọn các món sao cho cả hai điều kiện đều thỏa và tổng điểm lớn nhất. (Gợi ý: mảng dp có hai chỉ số dung lượng, và cả hai vòng for dung lượng đều chạy ngược.)
| Đầu vào | Dòng 1: ba số nguyên n, A, B (1 ≤ n ≤ 100, 1 ≤ A, B ≤ 100). n dòng tiếp theo: dòng thứ i gồm ba số nguyên a[i], b[i], v[i] (1 ≤ a[i], b[i] ≤ 100, 1 ≤ v[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng điểm lớn nhất. | |
| Test | Input | Output |
| 1 | 3 5 5 3 2 10 2 4 12 2 3 8 | 18 |
| 2 | 2 4 4 5 1 100 4 4 7 | 7 |
-
Gợi ý chung: Với mỗi bài túi, trước khi viết code em hãy tự trả lời ba câu: dp[j] nghĩa là gì, khởi tạo dp như thế nào, và vòng for theo j chạy xuôi hay ngược. Mỗi món chỉ lấy một lần thì chạy ngược. Dùng long long cho điểm và lấy phần dư khi đề yêu cầu. Hãy thử code với một bảng nhỏ vẽ bằng tay (như bảng 3 món ở Mẫu 2) trước khi nộp.
-
Gợi ý riêng: Chọn cỡ ba lô: sau khi xử lý hết các món, mảng dp một hàng đã chứa sẵn đáp án của mọi cỡ j, em chỉ cần in ra. Chia đôi kho báu: tìm các tổng j mà một bạn có thể nhận, rồi chọn j sao cho |T - 2j| nhỏ nhất. Chợ trái cây: coi k[i] quả giống nhau như k[i] món riêng. Số cách trả tiền và Những bước nhảy của Thỏ: hãy thử xu {1, 2}, S = 3 bằng tay để chọn thứ tự hai vòng for. Nhiều nhất k món: thêm một chỉ số đếm số món, mảng dp[c][j]. Ba lô khổng lồ: dp[x] là cân nặng nhỏ nhất để đạt ít nhất x điểm. Món đồ nặng như núi: dùng n ≤ 20 để duyệt mọi tập con. Ba lô hai ràng buộc: mảng dp[x][y] và cả hai vòng for đều chạy ngược.
-
Lưu ý thêm: Khi n × W vượt quá khoảng 108 thì DP theo cân nặng sẽ quá chậm, em hãy xem lại đề có cách khác không. Mảng dp có W + 1 phần tử, nhớ khai báo đủ. Khi cần in -1, hãy dùng một giá trị đặc biệt (-1 hoặc INF) để đánh dấu "chưa làm được" và kiểm tra nó trước khi cộng.