Cái túi giá trị tối đa
Points
18
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$. 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$.
Community Discussion