Cái túi đa ràng buộc

Buổi 22 — DP 2D & LIS Dynamic Programming
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Một nhà thám hiểm có một chiếc ba lô chịu được tổng trọng lượng tối đa $W$ và tổng thể tích tối đa $V$. Có $N$ món đồ, món đồ thứ $i$ có trọng lượng $w_i$, thể tích $u_i$ và giá trị $c_i$. Mỗi món đồ chỉ được chọn tối đa 1 lần. Hãy tìm tổng giá trị lớn nhất có thể mang theo.

Cấu trúc con tối ưu: $dp[w][v] = \max(dp[w][v], dp[w - w_i][v - u_i] + c_i)$ khi duyệt $w$ và $v$ giảm dần.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $N, W, V$. $N$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $w_i, u_i, c_i$.

Dữ liệu ra

Một số nguyên duy nhất là tổng giá trị lớn nhất.

Ví dụ
Input Output
3 5 6
2 3 10
3 2 15
4 4 22
25
2 3 3
4 1 10
1 4 10
0
Giới hạn

$1 \le N \le 100$, $1 \le W, V \le 200$, $1 \le w_i \le W$, $1 \le u_i \le V$, $1 \le c_i \le 10^9$.

Draft saved