Một tên trộm có một cái túi với sức chứa tối đa là . Tên trộm đột nhập vào một cửa hàng có món đồ, món đồ thứ có trọng lượng và giá trị . Tên trộm phải quyết định chọn hoặc không chọn mỗi món đồ (không thể lấy một phần). Hãy giúp tên trộm chọn các món đồ để tổng giá trị thu được là lớn nhất mà không vượt quá sức chứa của túi.
Hãy giải bài toán này bằng thuật toán Nhánh và Cận.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và .
dòng tiếp theo, mỗi dòng chứa hai số nguyên và .
Kết quả: Một số nguyên duy nhất là tổng giá trị lớn nhất có thể.
Ví dụ:
Ví dụ:
Dữ liệu:
4 10
5 10
4 40
6 30
3 50
Kết quả:
90
Giải thích: Chọn món đồ thứ (trọng lượng , giá trị ) và món đồ thứ (trọng lượng , giá trị ). Tổng trọng lượng là , tổng giá trị là .
