Cái túi 1 ver 2
Đề bài
Trong siêu thị tại gian hàng Black Friday có $n$ đồ vật, đồ vật thứ $i$ có trọng lượng là $W[i]$ và giá trị $V[i]$. Bạn được một phiếu mua hàng đặc biệt khi vào mua hàng tại gian hàng Black Friday ở siêu thị này. Khi sử dụng phiếu mua hàng này bạn được phép chọn một số đồ vật bất kỳ trên gian hàng miễn sao trọng lượng tối đa là $M$. Hỏi bạn có thể lấy đi những mặt hàng nào để giá trị bạn nhận được là tối đa.
Bạn hãy lập trình giải quyết bài toán trên với dữ liệu cho là danh sách $n$ mặt hàng tại gian hàng mà bạn có thể chọn.
Dữ liệu nhập:
- Dòng đầu tiên là hai số nguyên dương $n$ và $M$ $(1 \le n \le 25;\ 1 \le M \le 10^{11})$.
- Dòng thứ $i$ trong $n$ dòng tiếp theo chứa hai số nguyên $w[i]$ và $v[i]$ là trọng lượng và giá trị của đồ vật thứ $i$ $(1 \le w[i], v[i] \le 10^9)$.
Kết quả: in ra một số nguyên duy nhất là tổng giá trị tối đa của các vật phẩm mà bạn có thể chọn.
Ghi chú: ảnh đề gốc ghi giới hạn thời gian 3 giây, 128 MB; trên CLUE OJ bài đặt giới hạn 1 giây, 256 MB.
5 20
7 1
5 8
1 1
7 8
9 718Giải thích ví dụ: lấy 4 đồ vật đầu tiên, tổng trọng lượng $7 + 5 + 1 + 7 = 20 \le 20$, tổng giá trị $1 + 8 + 1 + 8 = 18$. Không có cách chọn nào được nhiều hơn (ví dụ lấy đồ vật 2, 4, 5 thì nặng $5 + 7 + 9 = 21 > 20$).
Lời mở đầu
Bài cái túi (knapsack) thường được giải bằng quy hoạch động theo trọng lượng, nhưng ở đây $M$ lên tới $10^{11}$ nên cách đó không dùng được. Bù lại $n \le 25$ rất nhỏ: mỗi đồ vật chỉ có 2 lựa chọn lấy hoặc không lấy, tổng cộng $2^{25} \approx 3{,}4 \cdot 10^7$ cách chọn – vừa đủ để quay lui thử hết. Mình sẽ so sánh cách duyệt bitmask (chậm hơn một chút vì mỗi cách chọn phải cộng lại $n$ số) với cách quay lui (cộng dồn khi đi xuống cây, lại cắt được nhánh quá tải).
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$ | $M$ lớn nhất | $w$ lớn nhất | $v$ lớn nhất | Đáp án lớn nhất |
|---|---|---|---|---|---|
| 1–30 | 5–10 | 29 | 10 | 10 | 52 |
| 31–50 | 15–15 | 989.867.216 | 997.543.379 | 942.203.320 | 1.697.237.779 |
| 51–70 | 20–20 | 397.248.584 | 935.832.228 | 961.185.807 | 2.210.867.315 |
| 71–100 | 25–25 | 959.216.042 | 999.840.189 | 999.247.976 | 5.002.061.563 |
Đề không ghi subtask, nhưng bộ test chia rất rõ thành 4 mức theo $n$, mình tự đặt tên là các mức dưới đây. Đáp án có thể vượt $2^{31}$ (tổng của tối đa 25 giá trị $10^9$), nên tổng trọng lượng, tổng giá trị đều phải là long long. Riêng $M$ tới $10^{11}$ – không làm quy hoạch động theo trọng lượng được, đây đúng là bài cho quay lui.
| Mức | Điều kiện | Test | Cách 1 (bitmask, C++) | Cách 2 (quay lui, C++) |
|---|---|---|---|---|
| 1 | $n \le 10$ | 1–30 | qua | qua |
| 2 | $n = 15$ | 31–50 | qua | qua |
| 3 | $n = 20$ | 51–70 | qua | qua |
| 4 | $n = 25$ | 71–100 | quá thời gian (~2,8 s) | qua (≤ 0,14 s) |
Ý tưởngCây nhị phân lấy / không lấy
Xét lần lượt đồ vật 1, 2, ..., $n$. Với mỗi đồ vật ta rẽ thành 2 nhánh: bỏ nó hoặc lấy nó. Đi hết $n$ tầng ta được một cách chọn, đem tổng giá trị so với kỷ lục best. Hàm quay lui:
- Nếu $i > n$: cập nhật
best = max(best, V). - Nhánh bỏ:
Try(i + 1, W, V). - Nhánh lấy – chỉ khi $W + w_i \le M$:
Try(i + 1, W + w[i], V + v[i]). Nếu túi đã không chứa nổi thì cả cây con bên dưới bị cắt bỏ.
Em nhập các đồ vật (mỗi đồ vật 2 số $w\ v$, tối đa 5 đồ vật) rồi bấm Tiếp. Mỗi nút ghi W/V hiện tại, nhánh trên là "bỏ", nhánh dưới là "lấy":
Cách 1Duyệt mọi tập con bằng bitmask (qua mức 1–3)
Mỗi số nguyên mask từ $0$ đến $2^n - 1$ ứng với một cách chọn: bit thứ $i$ bằng 1 nghĩa là lấy đồ vật $i$. Với mỗi mask, cộng trọng lượng và giá trị các đồ vật được chọn, nếu không quá $M$ thì cập nhật đáp án.
if(mask >> i & 1) cho từng bit (gộp luôn vòng for i).Kết quả chạy thật: đúng 70/100 test (mức 1, 2, 3). 30 test cuối có $n = 25$: $2^{25} \cdot 25 \approx 8{,}4 \cdot 10^8$ phép tính, chạy khoảng 2,8 giây → quá thời gian.
Cách 2Quay lui cộng dồn + cắt nhánh quá tải (full điểm)
Điểm yếu của cách 1 là mỗi tập con lại cộng lại từ đầu $n$ số. Quay lui thì cộng dồn: đi xuống một tầng chỉ tốn 1 phép cộng, nên tổng chi phí chỉ là số nút của cây ($\approx 2^{n+1}$). Thêm nữa, nhánh "lấy" chỉ được đi khi túi còn chứa nổi, nên rất nhiều cây con bị cắt bỏ.
- Tham số
W,Vtruyền theo giá trị nên khi quay lui về không cần "trừ lại" – mỗi lời gọi giữ bản sao riêng. - Dùng
long longchoM,W,V,best: $M$ tới $10^{11}$, tổng giá trị tới $2{,}5 \cdot 10^{10}$. - Độ sâu đệ quy chỉ $n + 1 = 26$ tầng, không lo tràn ngăn xếp.
Kết quả chạy thật: đúng 100/100 test, chậm nhất 0,14 giây. Kể cả trường hợp xấu nhất không cắt được nhánh nào ($2^{26}$ lời gọi) thì vẫn chỉ khoảng 0,3 giây.
Python thì sao?
Bản Python của cách 2 (khung code trên) đúng 91/100 test: 9 test $n = 25$ mà túi rộng (ít nhánh bị cắt) chạy 1,6–3,7 giây → quá thời gian. Để Python qua hết, mình dùng thêm kỹ thuật chia đôi tập (meet in the middle): chia đồ vật thành 2 nửa, mỗi nửa liệt kê tối đa $2^{13} = 8192$ tập con. Sắp xếp các tập của nửa phải theo trọng lượng, tính giá trị lớn nhất tiền tố; với mỗi tập của nửa trái (trọng lượng $W$) chặt nhị phân tìm tập nửa phải nặng nhất mà vẫn $\le M - W$. Độ phức tạp $O(2^{n/2} \cdot n)$.
Kết quả chạy thật: bản chia đôi tập bằng Python đúng 100/100 test, chậm nhất 0,033 giây.
Nhận xét
Đăng nhận xét