배낭 : 하나의 제약 조건, 각 항목은 많은 수의 항목으로 한 번만 선택할 수 있습니다.

Question

나는 배낭 문제 양식을 사용하는 알고리즘을 작성하고 있습니다. 나는 최대 무게 (W)가 주어진 내 배낭의 가치 (V)를 극대화하려고 노력하고 있습니다. 캐치는 각 항목 (I)을 한 번만 선택할 수 있으며 무게에 관계없이 배낭은 10 개의 항목 만 저장할 수 있으며 매우 많은 수의 항목 (500 개 이상)이 있습니다.

지금까지 생각 해봤 던 과체중 인 배낭을 생성하고, < = 최대 무게가 될 때까지 한 번에 하나씩 항목을 뒤쪽으로 재귀 적으로 작업했습니다. 이것은 가장 최적의 배낭을 만드는 데는 문제가되지 않지만, 다음과 같은 100 배 정도의 배낭을 생성하고 싶습니다. 나는 재귀 과정을 계속하여이 작업을 수행 할 수 있다고 생각했지만 약간 더 최적의 배낭이 누락 될 수 있으므로 완전히 정확하다고 느끼지는 않습니다.

Answer 1

이 문제는 정수 프로그램으로 공식화 할 수 있습니다.

maximize sum_{i in items} v_i * x_i 
subject to 
sum_{i in items} x_i <= 10  [u] 
sum_{i in items} w_i * x_i <= W [z] 
for all i in items, x_i in {0, 1} [y_i] 

이 프로그램을 해결할 수있는 많은 라이브러리가 있습니다. 또는 직접 branch and bound을 사용할 수 있습니다. 다음은 분기 및 경계에 필요한 정수 프로그램의 목표 값에 대한 상한값을 얻기 위해 해결할 수있는 이중 선형 프로그램입니다.

minimize 10 * u + W * z + sum_{i in items} y_i 
subject to 
for all i in items, u + w_i * z + y_i >= v_i [x_i] 
u >= 0 
z >= 0 
for all i in items, y_i >= 0 

다른 변수를 설정하면 열째 큰 값으로 할당하면서 u v_i - w_i * z하여 아홉 개 상위 항목 긍정적 y_i 할당의 문제, z 값을 감안. 시간이 O(n log n) 인 경우 z에 대한 3 진 검색이 가능해야합니다.