Chọn gói tối ưu
Xem dạng PDFCho ~N~ đối tượng, đối tượng thứ ~i~ có:
- thời gian đi một chiều là ~t_i~
- giá trị nhận được là ~e_i~
Nếu chọn đối tượng thứ ~i~, tổng thời gian tiêu tốn là ~2t_i~ và tổng giá trị nhận được tăng thêm ~e_i~.
Cho trước giới hạn thời gian ~T~. Mỗi đối tượng được chọn không quá một lần.
Yêu cầu
Hãy chọn một số đối tượng sao cho:
- tổng thời gian không vượt quá ~T~
- tổng giá trị nhận được là lớn nhất
Dữ liệu
- Dòng đầu chứa hai số nguyên dương ~N, T~
- ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~t_i, e_i~
Kết quả
In ra một số nguyên duy nhất là tổng giá trị lớn nhất có thể đạt được.
Ví dụ
Ví dụ 1
Input
5 18
6 93
15 41
3 2
17 61
5 66
Output
95
Ví dụ 2
Input
4 20
14 1
20 100
8 98
3 20
Output
98
Giải thích Ví dụ 1
Input: N=5, T=18
| Đối tượng | tᵢ | eᵢ | Chi phí (2·tᵢ) |
|---|---|---|---|
| 1 | 6 | 93 | 12 |
| 2 | 15 | 41 | 30 |
| 3 | 3 | 2 | 6 |
| 4 | 17 | 61 | 34 |
| 5 | 5 | 66 | 10 |
Giới hạn thời gian T = 18. Ta cần chọn một số đối tượng sao cho tổng chi phí ≤ 18 và tổng giá trị lớn nhất.
Loại ngay: Đối tượng 2 (chi phí 30) và đối tượng 4 (chi phí 34) đều vượt quá 18, nên không thể chọn riêng lẻ hay kết hợp.
Các tổ hợp hợp lệ còn lại:
- Chọn {1}: chi phí 12 ≤ 18 → giá trị = 93
- Chọn {3}: chi phí 6 ≤ 18 → giá trị = 2
- Chọn {5}: chi phí 10 ≤ 18 → giá trị = 66
- Chọn {1, 3}: chi phí 12 + 6 = 18 ≤ 18 → giá trị = 93 + 2 = 95 ✅
- Chọn {1, 5}: chi phí 12 + 10 = 22 > 18 → loại
- Chọn {3, 5}: chi phí 6 + 10 = 16 ≤ 18 → giá trị = 2 + 66 = 68
- Chọn {1, 3, 5}: chi phí 12 + 6 + 10 = 28 > 18 → loại
Phương án tối ưu: Chọn đối tượng 1 (t=6, e=93) và đối tượng 3 (t=3, e=2). Tổng thời gian 2·6 + 2·3 = 18, vừa khít giới hạn. Tổng giá trị = 95. ✅
Giải thích Ví dụ 2
Input: N=4, T=20
| Đối tượng | tᵢ | eᵢ | Chi phí (2·tᵢ) |
|---|---|---|---|
| 1 | 14 | 1 | 28 |
| 2 | 20 | 100 | 40 |
| 3 | 8 | 98 | 16 |
| 4 | 3 | 20 | 6 |
Giới hạn thời gian T = 20.
Duyệt tất cả tổ hợp:
- Chọn {1}: chi phí 28 > 20 → loại
- Chọn {2}: chi phí 40 > 20 → loại
- Chọn {3}: chi phí 16 ≤ 20 → giá trị = 98 ✅
- Chọn {4}: chi phí 6 ≤ 20 → giá trị = 20
- Chọn {3, 4}: chi phí 16 + 6 = 22 > 20 → loại
- Chọn {1, 4}: chi phí 28 + 6 = 34 > 20 → loại
- Mọi tổ hợp khác đều có chi phí ≥ 28 → loại
Phương án tối ưu: Chọn duy nhất đối tượng 3 (t=8, e=98). Tổng thời gian 2·8 = 16 ≤ 20. Tổng giá trị = 98.
Ràng buộc và chấm điểm
Ràng buộc
- ~1 \le N \le 100~
- ~1 \le T \le 100~
- ~0 \le t_i \le 10^3~
- ~1 \le e_i \le 10^3~
Chấm điểm
- Có ~30%~ số test, tương ứng ~30%~ số điểm, có ~N \le 10~ và ~T \le 20~
- Có ~40%~ số test, tương ứng ~40%~ số điểm, có ~10 < N \le 10^2~ và ~20 < T \le 10^2~
- Có ~30%~ số test, tương ứng ~30%~ số điểm, có ~N \ge 10^2~ và ~T \ge 10^2~
Bình luận
Ví dụ 2 sai và cho em xin test 17 được không ạ?
Đã fix