Knapsack 2
Đề 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^9)$: 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^3)$ 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 60901 1000000000
1000000000 10106 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 (khối lượng $3 + 5 = 8$, giá trị $30 + 60 = 90$); ví dụ 3 chọn đồ vật 2, 4, 5 (khối lượng $5 + 6 + 3 = 14$, giá trị $6 + 6 + 5 = 17$).
Lời mở đầu
Đề giống hệt Knapsack 1, chỉ đổi giới hạn: $W$ lên tới $10^9$ nhưng giá trị $v_i \le 10^3$. Chỉ một thay đổi nhỏ đó làm cách QHĐ theo khối lượng sụp đổ hoàn toàn (mảng $10^9$ phần tử!). Bài học của bài này rất quan trọng: khi một chiều trạng thái quá lớn, hãy thử đổi vai – lấy đại lượng nhỏ làm chỉ số mảng, đại lượng lớn làm giá trị lưu trong mảng.
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$ | $v_i$ lớn nhất | $\sum v_i$ lớn nhất | Đáp án lớn nhất |
|---|---|---|---|---|---|
| 1–20 | 3–18 | 6–96 | 100 | 968 | 449 |
| 21–80 | 100–100 | 119.865.234–984.077.807 | 999 | 25.502 | 25.195 |
| 81–100 | 100–100 | 1.000.000.000–1.000.000.000 | 986 | 27.764 | 25.375 |
Giống Knapsack 1, bộ test có 2 mức: 20 test đầu rất nhỏ ($W < 100$), 80 test sau $N = 100$ và $W$ rất lớn (20 test cuối $W = 10^9$). Điểm mấu chốt nằm ở cột $\sum v_i$: tổng giá trị mọi đồ vật chỉ khoảng $2{,}8 \cdot 10^4$ (lý thuyết tối đa $100 \cdot 10^3 = 10^5$) – nhỏ hơn $W$ cả chục nghìn lần.
| Mức | Điều kiện | Test | Cách 1 vét cạn | Cách 2 QHĐ theo khối lượng | Cách 3 QHĐ theo giá trị |
|---|---|---|---|---|---|
| 1 | $N \le 18,\ W \le 96$ | 1–20 | qua | qua | qua |
| 2 | $N = 100,\ W \le 10^9$ | 21–100 | quá thời gian | hết bộ nhớ / quá thời gian | qua (0,01 s) |
Ý tưởngĐổi vai: dp[s] = khối lượng nhỏ nhất để đạt giá trị s
Ở Knapsack 1 ta hỏi: "với sức chứa $c$, được giá trị lớn nhất là bao nhiêu?". Giờ ta hỏi ngược lại: "muốn có đúng tổng giá trị $s$ thì cần khối lượng nhỏ nhất là bao nhiêu?". Tổng giá trị tối đa chỉ $S = \sum v_i \le 10^5$ nên mảng có $S + 1$ ô là đủ.
dp[i][s] = khối lượng nhỏ nhất khi chọn trong $i$ đồ vật đầu để tổng giá trị đúng bằng $s$ ($\infty$ nếu không thể).
$$dp[i][s] = \min\big(dp[i-1][s],\ dp[i-1][s - v_i] + w_i\big)$$
Cơ sở: $dp[0][0] = 0$, $dp[0][s] = \infty$ với $s > 0$. Đáp án là $s$ lớn nhất sao cho $dp[N][s] \le W$.Em nhập $W$ và các đồ vật (giá trị nhỏ thôi để bảng vừa màn hình), bấm Tiếp để xem bảng điền từng ô, bước cuối dò hàng cuối tìm giá trị lớn nhất mà khối lượng không vượt $W$:
Cách 1Vét cạn lấy / không lấy (mức 1)
Vẫn là quay lui như Knapsack 1, chỉ cần nhớ tổng khối lượng có thể vượt int ($100 \cdot 10^9$) nên dùng long long.
Kết quả chạy thật: đúng 20/100 test – qua 20 test nhỏ, 80 test $N = 100$ bị quá thời gian.
Cách 2Dùng lại QHĐ theo khối lượng của Knapsack 1 (mức 1)
Thử nộp nguyên lời giải mảng 1 chiều của Knapsack 1, xem chuyện gì xảy ra:
Kết quả chạy thật: đúng 20/100 test. Với 20 test nhỏ thì vẫn đúng, nhưng khi $W$ cỡ $10^8$–$10^9$, chỉ riêng mảng dp đã cần $8 \cdot 10^9$ byte = 8 GB – vượt xa 1 GB (mình chạy với giới hạn bộ nhớ 1 GB thì chương trình chết ngay khi cấp phát), chưa kể $N \cdot W = 10^{11}$ phép tính. Cụ thể: 77 test bị lỗi cấp phát bộ nhớ, 3 test có $W$ khoảng $1{,}2 \cdot 10^8$ (mảng vừa đủ 1 GB) thì quá thời gian.
Cách 3QHĐ theo giá trị (full điểm)
Cài đặt công thức ở phần ý tưởng bằng một mảng 1 chiều dp[s], duyệt $s$ giảm dần (giống hệt mẹo ở Knapsack 1 để mỗi đồ vật chỉ được lấy 1 lần):
INF = 1e18đánh dấu "không đạt được"; cộng thêm $w_i \le 10^9$ vẫn không trànlong long.- Kích thước mảng là $S + 1$ với $S = \sum v_i \le 10^5$ – chỉ cỡ 800 KB.
- Vòng cuối duyệt $s$ tăng dần, gặp
dp[s] <= Wthì cập nhậtans = s, nên cuối cùnganslà giá trị lớn nhất mang được.
Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0,01 giây. Bản Python (mình viết thêm, cũng dùng list comprehension cho cả đoạn) đúng 100/100 test, chậm nhất 0,29 giây.
Nhận xét
Đăng nhận xét