Cái túi vừa khít

Buổi 22 — DP 2D & LIS Dynamic Programming
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$.

Draft saved