Hành trang leo núi dã ngoại

Buổi 21 — DP 1D cổ điển Buổi 22 — DP 2D & LIS Dynamic Programming
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions

Bài toán cái túi 0/1

Có $N$ món đồ được đánh số từ $1$ đến $N$. Món đồ thứ $i$ có trọng lượng $w_i$ và giá trị $v_i$.

Bạn có một cái túi có sức chứa tối đa là $W$. Hãy chọn một tập hợp các món đồ để cho vào túi 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 có thể.

Dữ liệu vào

  • Dòng 1: Hai số nguyên $N$ và $W$ ($1 \le N \le 1000, 1 \le W \le 1000$).
  • $N$ dòng tiếp theo: Mỗi dòng chứa hai số nguyên $w_i$ và $v_i$ ($1 \le w_i \le W, 1 \le v_i \le 10^6$).

Dữ liệu ra

In ra một số nguyên duy nhất là tổng giá trị lớn nhất có thể đạt được.

Draft saved