Xếp đồ vào ba lô

Buổi 11 — Brute Force & Sinh tổ hợp Implementation
Points
60
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
recursion
Submissions
Đề bài

Có $N$ đồ vật, mỗi đồ vật có trọng lượng $w_i$ và giá trị $v_i$. Ba lô chịu được tối đa trọng lượng $W$. Tìm giá trị lớn nhất có thể mang theo.

Dùng phương pháp duyệt nhánh cận (branch and bound) hoặc Meet in the Middle.

Dữ liệu vào
  • Dòng đầu: hai số nguyên $N$ và $W$ $(1 \le N \le 40, 1 \le W \le 10^{15})$.
  • $N$ dòng tiếp theo, mỗi dòng hai số $w_i$ và $v_i$ $(1 \le w_i, v_i \le 10^{15})$.
Dữ liệu ra
  • Một số nguyên — giá trị lớn nhất.
Ví dụ
Input Output
4 10\n3 4\n4 5\n5 7\n2 3 12
3 5\n6 10\n7 20\n8 30 0
Giới hạn
  • $1 \le N \le 40$
  • $1 \le W \le 10^{15}$
  • $1 \le w_i, v_i \le 10^{15}$
Draft saved