Tôi có vấn đề trên bề mặt trông giống như 0-1 ba lô. Tôi có một tập hợp các "ứng cử viên" có thể được chọn (hoặc không), mỗi ứng cử viên có một "trọng lượng" (chi phí) và một "giá trị tiềm năng". Đây có phải là toàn bộ vấn đề, tôi muốn sử dụng một phương pháp DP và được thực hiện với nó. Nhưng đây là curveball: Có "hạn chế phân vùng" trên các ứng cử viên có thể có trong giải pháp cuối cùng.0-1 Knapsack w/ràng buộc phân vùng
Ý tôi là không gian ứng cử viên được chia thành các lớp tương đương rời rạc. Đối với vấn đề cụ thể của tôi có khoảng 300 ứng cử viên và 12 lớp tương đương có thể. Có "quy tắc kinh doanh" có nghĩa là tôi chỉ có thể nói 3 ứng cử viên từ các ứng cử viên C1 và 6 từ C2, v.v.
Ràng buộc này gợi ý cách tiếp cận kiểu tìm kiếm đồ thị bằng kỹ thuật chi nhánh và ràng buộc hoặc một số hình thức cắt tỉa khác, tuy nhiên tôi hơi bối rối như thế nào để bắt đầu kể từ khi tôi chỉ quen thuộc với các giải pháp DP 0-1 Knapsack. Kỹ thuật/phương pháp nào có thể phù hợp cho vấn đề này? Tôi cũng nghĩ rằng có thể sử dụng một thư viện lập trình hạn chế nhưng tôi không chắc chắn nếu nó sẽ có thể tìm thấy một giải pháp?