Bounded Knapsack Problem 설정. 원하는 모든 포장 목록

Question

무엇이든 최적화하는 것이 아니라 배낭의 "불완전"포장을 포함하여 가능한 모든 것을 나열하고 싶습니다. 물론 객체 집합의 모든 하위 집합을 반복하고 가중치 제약 조건을 만족하는 항목을 선택할 수 있습니다 (하위 집합의 크기에 대한 상한을 설정하여 개선 할 수 있음). 그러나 더 많은 것을 원합니다. 실력 있는.

감사합니다.

Answer 1

먼저 개체를 무게별로 정렬하십시오. 그런 다음 배낭을 반복적으로 포장합니다. 아직 고려되지 않은 가장 작은 가중치 오브젝트가 맞지 않거나 남아있는 오브젝트가없는 경우 현재의 배낭을 우리의 목록에 추가하고 리턴하십시오. 그렇지 않으면 목록에있는 모든 오브젝트를 넣고 현재의 배낭을 목록에 추가하십시오 배낭의 나머지 부분을 포장 한 마지막 물건보다 무거운 물건으로 포장하십시오.

주어진 유형의 항목을 두 개 이상 포장 할 수있는 경우보다 작거나 같음으로 대체하십시오.

동일한 가중치를 가진 여러 객체가있는 경우 먼저 가중치로 정렬 한 다음 임의의 순서로 정렬하고이를 사용해야합니다.

PackKnapsack(knapsack, objects) 
    add knapsack to list 
    if objects is empty return 
    if smallest object does not fit return 
    for each object in order from smallest to largest 
     if currentobject does not fit 
     break 
     PackKnapsack(knapsack + currentObject, objects heavier than current object)