Bài toán ba lô 4
Xem PDF
Điểm:
2000 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Trong siêu thị có \(N\) đồ vật, đồ vật thứ \(i\) có khối lượng là \(W_i\), và có giá trị là \(V_i\). Một ngày, CJ vào siêu thị để mua đồ. Vì trước kia mua nhiều ở đây, nên CJ được một tấm thẻ đặc biệt của siêu thị. Khi có tấm thẻ này thì CJ được quyền lấy một số món đồ sao cho tổng khối lượng không quá \(M\). Vì CJ không giỏi tính toán, nên các bạn hãy giúp CJ lấy một số món đồ sao cho tổng khối lượng không quá \(M\), và tổng giá trị lớn nhất có thể.
Input
- Dòng thứ nhất chứa hai số nguyên dương \(N, M\) là số món đồ trong siêu thị và tổng khối lượng tối đa trong tấm thẻ.
- \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(W_i\), \(V_i\) lần lượt là khối lượng và giá trị của đồ vật thứ \(i\).
Output
- Dòng thứ nhất in ra số món đồ mà CJ lấy để tổng giá trị đạt lớn nhất.
- Dòng thứ hai in ra chỉ số các món đồ mà CJ lấy theo thứ tự tăng dần.
Scoring
- \(M \leq 15.10^9\), \(W_i, V_i \leq 10^9\), với \(\forall i, 1 \leq i \leq N\).
- Subtask \(1\) (\(50\%\) số điểm): \(N \leq 18\).
- Subtask \(2\) (\(50\%\) số điểm): \(N \leq 36\).
Example
Test 1
Input
5 20
7 1
5 8
1 1
7 8
9 7Output
4
1 2 3 4
Bình luận
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.