제약 조건의 배낭 문제

Question

0/1 배낭 문제에 익숙합니다. 그러나 다음의 제약 조건이 부과되면 ... 질문을 어떻게 해결할 수 있습니까?

1. 일부 항목을 선택하면 'u'를 선택하면 다른 항목 'V'를 선택할 수 없습니다.
예를 들어

항목은 [이름, 무게, 가치]로 주어집니다
항목은 다음과 같습니다 :
A 10 20
B 50 80
C 20 30
D 30 70
E 50 50

B를 선택하면 A를 선택할 수 없습니다. e를 선택하면 C를 선택할 수 없습니다. D를 선택하면 A를 선택할 수 없습니다. 유사한 방식으로 제약 조건이 제공됩니다.


위의 문제를 해결할 수있는 방법을 좀주세요.어떤 도움도 높이 평가됩니다.

Answer 1

표준 동적 프로그래밍 접근법은이 문제에 대해 작동하지 않을 것입니다. 왜냐하면 여분의 "이 또는 두 구속 조건이 겹치는 서브 프로 뷰 속성. 그래서 슬레지 해머를 끊어 봅시다.

이를 0-1 정수 선형 프로그래밍 문제점을 눌러 사용하고 선반 솔버. 주어진 예 (및 최대 무게 제한 $ W $ )에 대해서는 적절한 0-1 ILP 문제가 있습니다 :

최대화 $ 20A + 80B + 30C + 70D + 50E $


$ A, B, C, D, e \ in \ {0, 1 \} $ $ 10a + 50b + 20c + 30d + 50e \ le W $
$ A + B \ LE 1 $
$ C + E \ LE 1 $
$ A + D \ LE 1 $

정수 선형 프로그래밍 솔버가 문제의 구조를 최대한 활용할 것이라는 것은 나에게 명백하지 않습니다. 따라서 아마도보다 전문화 된 솔루션이 실제로 더 잘 수행 될 수 있습니다.