Balo 0/1 sức chứa khổng lồ

Dynamic Programming
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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 balo có sức chứa tối đa $W$. Hãy chọn ra một tập hợp các món đồ sao cho tổng trọng lượng không vượt quá $W$ và tổng giá trị thu được là lớn nhất. Lưu ý rằng $W$ có thể rất lớn, nhưng giá trị $v_i$ của mỗi món đồ lại nhỏ.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $W$.
  • $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $w_i$ và $v_i$.
Dữ liệu ra
  • In ra tổng giá trị lớn nhất có thể đạt được.
Ví dụ
Dữ liệu vào Dữ liệu ra
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 w_i \le 10^9$
  • $1 \le v_i \le 1000$
Draft saved