Bài toán cái túi không lặp
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Có $N$ món đồ, món đồ thứ $i$ có trọng lượng $w_i$ và giá trị $v_i$. Bạn có một chiếc túi có thể chứa tối đa tổng trọng lượng là $W$. Mỗi món đồ chỉ có thể được chọn tối đa một lần.
Hãy tìm tổng giá trị lớn nhất của các món đồ có thể mang theo trong túi.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $W$ ($1 \le N \le 200$, $1 \le W \le 10^4$).
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $w_i$ và $v_i$ ($1 \le w_i \le 10^4$, $1 \le v_i \le 10^9$).
Dữ liệu ra
- In ra một số nguyên duy nhất là tổng giá trị lớn nhất có thể đạt được.
Ví dụ
| Input | Output |
|---|---|
| 3 8 3 30 4 50 5 60 |
90 |
Giới hạn
- $1 \le N \le 200$
- $1 \le W \le 10^4$
- $1 \le w_i \le 10^4$
- $1 \le v_i \le 10^9$
Community Discussion