Ba Lô 0/1 Trọng Lượng Lớn

Buổi 75-76 — Stress Test Dynamic Programming
Points
32
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Có $N$ đồ vật, vật thứ $i$ có khối lượng $w_i$ và giá trị $v_i$. Bạn có một chiếc ba lô sức chứa tối đa $W$. Hãy chọn một tập các đồ vật có tổng khối lượng không vượt quá $W$ sao cho tổng giá trị lớn nhất có thể.

Chú ý: $W$ rất lớn (lên tới $10^9$), không thể tạo mảng dp[W].

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N$ và $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
  • In ra một số nguyên duy nhất là tổng giá trị lớn nhất.
Ví dụ
Input Output
3 1000000000
600000000 10
500000000 8
500000000 8
16
Giới hạn
  • $1 \le N \le 100$, $1 \le W \le 10^9$, $1 \le w_i \le 10^9$, $1 \le v_i \le 1000$
Draft saved