Cái túi vừa khít
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Có $N$ đồ vật, đồ vật thứ $i$ có trọng lượng $w_i$ và giá trị $v_i$. Mỗi đồ vật chỉ được chọn tối đa 1 lần. Bạn cần chọn một tập đồ vật sao cho tổng trọng lượng bằng đúng $W$ và tổng giá trị là lớn nhất có thể. Nếu không có cách chọn nào đạt đúng tổng trọng lượng $W$, in ra -1.
Cấu trúc con tối ưu: khởi tạo $dp[0] = 0$, $dp[s] = -\infty$ với $s > 0$, và cập nhật $dp[s] = \max(dp[s], dp[s - w_i] + v_i)$.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên $N, W$. $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $w_i, v_i$.
Dữ liệu ra
Tổng giá trị lớn nhất đạt đúng trọng lượng $W$, hoặc -1 nếu vô nghiệm.
Ví dụ
| Input | Output |
|---|---|
| 4 7 2 10 3 15 5 30 4 20 |
40 |
| 3 5 2 10 4 20 6 30 |
-1 |
Giới hạn
$1 \le N \le 500$, $1 \le W \le 10^4$, $1 \le w_i \le W$, $1 \le v_i \le 10^9$.
Community Discussion