Cái túi nhị phân cơ bản

Buổi 22 — DP 2D & LIS Dynamic Programming
Points
10
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Có $N$ đồ vật, đồ vật thứ $i$ có trọng lượng $w_i$. Bạn có một cái túi có sức chứa tối đa là $W$. Mỗi đồ vật chỉ được chọn tối đa một lần. Hãy tìm tổng trọng lượng lớn nhất có thể xếp vào túi sao cho không vượt quá $W$.

Cấu trúc con tối ưu: $dp[i][s]$ cho biết có thể đạt được tổng trọng lượng $s$ từ $i$ đồ vật đầu tiên hay không.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N, W$. Dòng thứ hai chứa $N$ số nguyên $w_1, w_2, \dots, w_N$.

Dữ liệu ra

Một số nguyên duy nhất là tổng trọng lượng lớn nhất không vượt quá $W$.

Ví dụ
Input Output
4 10
3 4 5 7
10
3 5
6 7 8
0
Giới hạn

$1 \le N \le 100$, $1 \le W \le 10000$, $1 \le w_i \le 10000$.

Draft saved