Cái túi trọng lượng lớn

General
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho $N$ đồ vật, đồ vật thứ $i$ có trọng lượng $w_i$ và giá trị $v_i$. Sức chứa của ba lô là $W$ (có thể lên tới $10^9$), nhưng giá trị mỗi món đồ tương đối nhỏ.

Hãy chọn các đồ vật (mỗi món tối đa 1 lần) sao cho tổng trọng lượng không vượt quá $W$ và tổng giá trị là lớn nhất.

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<br>3 30<br>4 50<br>5 60 90
Giới hạn
  • $1 \le N \le 100$
  • $1 \le W \le 10^9$
  • $\sum v_i \le 10^5$
Draft saved