부분 집합 합계의 변형입니다. (여러 제약)

Question

제가 해결하기 위해 노력하고있는 정상 부분 집합 합 문제에 당신에게 변화의 예를 들어 보겠습니다 : 감안할 때

이 = {1,2,3 S 세트입니다, ,

1. S1 = {2,3 : 4,5,6,7,8,9} 최대 용량 (C0) = 40과는 또 우리 3 개 가지 부분 집합 3 개 추가적인 제약 S을 4} 제약 조건 c1 = 5
2. S2 = {3 제약 조건 (C2)과 4,5,6} = 12
3. S3 = {7,8,9}로 제한 C3 = 25

목적은 S되도록들의 서브 세트를 찾는 것이다

• 교차로 possib 있습니다 : - (C4 C0) 중요

  총 합계 (포함 된 항목) 모든 주어진 제약 조건을 초과하지 않고 극대화 르! (S1 & S2 참조)

• 3은 제약 수 계산의 한 예일뿐입니다. S의 항목 비록
• 정수 값이 예에서, 또한 수 양의 실수
있습니다

질문 : 이 특정 부분 집합 합 문제가 특정 이름을 가지고 및/또는이다합니까 이것에 대한 논문/논문 리뷰가 있습니까?

Answer 1

이 배낭 문제 같은 소리 :

이

"부분 집합 합 문제가 특별한 결정의 경우 0-1 문제입니다 : https://en.wikipedia.org/wiki/Knapsack_problem

이 부분 집합 합 문제에 그 문서의 섹션을 참조하십시오 각 종류의 항목에서 가중치는 값과 같습니다. [...] 암호화 분야에서 용어 배낭 문제는 하위 집합 합계 문제를 구체적으로 나타 내기 위해 사용되며 일반적으로 Karp의 21 NP 완전 문제 중 하나로 알려져 있습니다. [30]

부분 집합 총 문제의 일반화는 다중 부분 집합 합계 렘은 같은 용량의 여러 개의 저장소가 존재합니다. 일반화에는 FPTAS가없는 것으로 나타났습니다. "[0123]"