Cái túi tối đa K món
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề 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 chiếc ba lô sức chứa $W$, nhưng ba lô chỉ chứa được tối đa $K$ món đồ (mỗi món chọn tối đa 1 lần).
Hãy tìm tổng giá trị lớn nhất có thể mang theo.
Dữ liệu vào
- Dòng đầu chứa ba số nguyên $N, W, K$ ($1 \le K \le N \le 100$, $1 \le W \le 1000$).
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $w_i, v_i$ ($1 \le w_i \le 1000$, $1 \le v_i \le 10^9$).
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 |
|---|---|
4 10 2<br>3 10<br>4 12<br>5 15<br>2 8 |
27 |
Giới hạn
- $1 \le K \le N \le 100$
- $1 \le W \le 1000$
Community Discussion