Cái túi giá trị tối đa

Buổi 22 — DP 2D & LIS Dynamic Programming
Points
18
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$. Bạn có một cái túi có sức chứa tối đa $W$. Mỗi đồ vật chỉ được chọn tối đa 1 lần. Hãy tìm tổng giá trị lớn nhất có thể đạt được sao cho tổng trọng lượng không vượt quá $W$.

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

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

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

Ví dụ
Input Output
3 8
3 30
4 50
5 60
90
4 5
2 3
3 4
4 5
5 6
7
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