Ba lô sức chứa khổng lồ
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho $N$ món đồ, món thứ $i$ có trọng lượng $w_i$ và giá trị $v_i$. Sức chứa của ba lô là $W$ rất lớn (lên tới $10^9$), nhưng giá trị của mỗi món đồ lại nhỏ ($v_i \le 1000$). Mỗi món đồ chỉ được chọn tối đa 1 lần.
Tìm tổng giá trị lớn nhất có thể mang theo mà tổng trọng lượng không vượt quá $W$.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, W$ ($1 \le N \le 100, 1 \le W \le 10^9$).
- $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 10^9, 1 \le v_i \le 1000$).
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 |
Giới hạn
- $1 \le N \le 100, 1 \le W \le 10^9, 1 \le v_i \le 1000$
Community Discussion