Knapsack 1
Đề bài
Có $N$ đồ vật được đánh số từ $1$ đến $N$. Đồ vật thứ $i$ $(1 \le i \le N)$ có khối lượng là $w_i$ và giá trị là $v_i$.
Taro quyết định chọn một số đồ vật bỏ vào chiếc túi của anh mang về. Sức chứa tối đa của chiếc túi là $W$, nghĩa là tổng khối lượng các đồ vật có thể mang tối đa là $W$.
Hãy tìm tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.
Input
- Dòng đầu tiên chứa hai số nguyên $N$ $(1 \le N \le 100)$ và $W$ $(1 \le W \le 10^5)$: số lượng đồ vật và sức chứa tối đa của chiếc túi.
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $w_i$ $(1 \le w_i \le W)$ và $v_i$ $(1 \le v_i \le 10^9)$ lần lượt là khối lượng và giá trị của đồ vật thứ $i$.
Output: xuất ra tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.
Giới hạn trên CLUE OJ: 2 giây, bộ nhớ 1 GB.
3 8
3 30
4 50
5 60905 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 100000000050000000006 15
6 5
5 6
6 4
6 6
3 5
7 217Giải thích: ở ví dụ 1 chọn đồ vật 1 và 3, tổng khối lượng $3 + 5 = 8$, tổng giá trị $30 + 60 = 90$. Ví dụ 2 cho thấy kết quả có thể vượt quá giới hạn kiểu số nguyên 32-bit. Ở ví dụ 3 chọn đồ vật 2, 4 và 5: tổng khối lượng $5 + 6 + 3 = 14$, tổng giá trị $6 + 6 + 5 = 17$.
Lời mở đầu
Đây là bài cái túi 0/1 kinh điển – bài "nhập môn" bắt buộc của chương quy hoạch động. Mỗi đồ vật chỉ có 2 lựa chọn: lấy hoặc không lấy. Mình sẽ đi đúng con đường mà các bạn nên đi với mọi bài QHĐ: bắt đầu từ vét cạn (đúng nhưng chậm), nhận ra các trạng thái bị tính lặp lại nên thêm bộ nhớ (đệ quy có nhớ), rồi lật ngược lại thành bảng QHĐ điền từ dưới lên, cuối cùng rút gọn bộ nhớ còn một mảng 1 chiều.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Test | $N$ | $W$ | $w_i$ lớn nhất | $v_i$ lớn nhất | Đáp án lớn nhất |
|---|---|---|---|---|---|
| 1–20 | 1–19 | 5–96 | 93 | 100 | 492 |
| 21–80 | 100–100 | 10.238–96.252 | 93.395 | 998.952.268 | 10.688.136.015 |
| 81–100 | 100–100 | 100.000–100.000 | 99.693 | 994.037.459 | 10.106.776.677 |
Đề không ghi subtask nhưng bộ test chia làm 2 mức rất rõ: 20 test đầu rất nhỏ ($N \le 19$, $W < 100$), 80 test sau đều có $N = 100$ và $W$ lớn (20 test cuối $W = 10^5$ đúng bằng giới hạn). Đáp án lên tới gần $10^{11}$ – vượt xa int, nên giá trị phải lưu bằng long long (đề cũng nhắc ở ví dụ 2).
| Mức | Điều kiện | Test | Cách 1 vét cạn | Cách 2 đệ quy có nhớ | Cách 3 bảng 2 chiều | Cách 4 mảng 1 chiều |
|---|---|---|---|---|---|---|
| 1 | $N \le 19,\ W \le 96$ | 1–20 | qua | qua | qua | qua |
| 2 | $N = 100,\ W \le 10^5$ | 21–100 | quá thời gian | qua (0,31 s) | qua (0,05 s) | qua (0,01 s) |
Ý tưởngBảng dp[i][c]: i đồ vật đầu, túi sức chứa c
Gọi dp[i][c] là tổng giá trị lớn nhất khi chỉ được chọn trong $i$ đồ vật đầu tiên và túi có sức chứa $c$. Xét đồ vật thứ $i$ (khối lượng $w_i$, giá trị $v_i$), chỉ có 2 khả năng:
- Không lấy đồ vật $i$: túi vẫn còn sức chứa $c$ cho $i - 1$ đồ vật đầu →
dp[i-1][c](ô ngay phía trên). - Lấy đồ vật $i$ (chỉ khi $w_i \le c$): mất $w_i$ sức chứa, được $v_i$ →
dp[i-1][c - w[i]] + v[i](ô chéo ở hàng trên, lùi trái $w_i$ cột).
dp[0][c] = 0 (chưa có đồ vật nào). Đáp án: dp[N][W].Em nhập sức chứa $W$ và các đồ vật (mỗi đồ vật 2 số $w\ v$) rồi bấm Tiếp để xem bảng được điền từng ô. Bước cuối mình truy vết ngược từ dp[N][W] để biết đã lấy những đồ vật nào:
Cách 1Vét cạn: thử lấy / không lấy từng đồ vật (mức 1)
Cách tự nhiên nhất: hàm Try(i, sw, sv) xét đồ vật $i$, rẽ 2 nhánh không lấy và lấy (nếu túi còn chứa nổi). Đi hết $N$ đồ vật thì cập nhật kỷ lục.
Kết quả chạy thật: đúng 20/100 test – qua hết mức 1 (cả 20 test đều dưới 0,01 giây), nhưng 80 test có $N = 100$ thì $2^{100}$ nhánh là không tưởng → quá thời gian.
Cách 2Đệ quy có nhớ (full điểm)
Để ý: kết quả của nhánh con chỉ phụ thuộc vào đồ vật đang xét $i$ và sức chứa còn lại $c$, chứ không phụ thuộc vào việc trước đó đã lấy đồ vật nào. Có rất nhiều đường đi khác nhau dẫn tới cùng một cặp $(i, c)$ – vét cạn tính đi tính lại chúng. Ta đổi hàm thành trả về giá trị:
memo[i][c], lần sau gặp lại trả về ngay.memset(memo, -1, ...): đánh dấu mọi ô "chưa tính". Giá trị thật luôn $\ge 0$ nên dùng $-1$ làm cờ được.- Chỉ có tối đa $N \cdot (W + 1) \approx 10^7$ trạng thái, mỗi trạng thái tính 1 lần với $O(1)$ phép toán.
- Mảng
memolàlong long$101 \times 100\,005$ ≈ 81 MB – vừa giới hạn 1 GB. Độ sâu đệ quy chỉ $N + 1 = 101$ tầng.
Kết quả chạy thật: đúng 100/100 test, chậm nhất 0,31 giây.
Cách 3QHĐ bảng 2 chiều (điền từ trên xuống)
Thay vì để đệ quy tự tìm thứ tự tính, ta điền bảng dp[i][c] theo từng hàng $i = 1, 2, \dots, N$: khi tính hàng $i$ thì hàng $i - 1$ đã có đủ. Đây chính là bảng trong phần ý tưởng.
- Mảng toàn cục nên
dp[0][c] = 0sẵn – đúng cơ sở QHĐ. - Gán trước
dp[i][c] = dp[i-1][c](không lấy), rồi mới so với phương án lấy – nhờ vậy ô có $c < w_i$ cũng có giá trị đúng. - Không đệ quy, không kiểm tra "đã tính chưa" nên nhanh hơn cách 2 một chút.
Kết quả chạy thật: đúng 100/100 test, chậm nhất 0,05 giây.
Cách 4Rút gọn còn mảng 1 chiều
Hàng $i$ chỉ dùng hàng $i - 1$, nên chỉ cần một mảng dp[c]: trước khi xử lý đồ vật $i$ nó chứa hàng $i-1$, xử lý xong thì thành hàng $i$. Bí quyết là duyệt $c$ giảm dần từ $W$ về $w_i$: khi cập nhật dp[c] ta đọc dp[c - w] ở bên trái – ô đó chưa bị sửa trong lượt này nên vẫn là giá trị của hàng $i - 1$.
dp[c - w] có thể đã được cập nhật bằng chính đồ vật $i$ → một đồ vật bị lấy nhiều lần (đó lại là bài cái túi không giới hạn). Với ví dụ 1, duyệt tăng sẽ in ra $100$ (lấy đồ vật 2 tới hai lần: $4 + 4 = 8$, $50 + 50 = 100$) thay vì $90$ – sai.Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0,01 giây, bộ nhớ chỉ còn $O(W)$. Bản Python (mình viết thêm) dùng list comprehension để tính cả đoạn $c = w..W$ một lần, đúng 100/100 test, chậm nhất 1,25 giây – vẫn trong giới hạn 2 giây.
long long cho giá trị – đáp án có test gần $10^{11}$.
Nhận xét
Đăng nhận xét