Cái túi đa ràng buộc
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề 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$.
Community Discussion