배낭에서 요소를 찾는 방법 (요소를 얻는 모든 방법에 꼬임 필요)

Question

이것은 동적 프로그래밍 접근법을 사용하여 해결 한 고전적인 배낭 문제입니다.

here에이어서, 나는 배낭을 구성하는 요소의 유형을 결정하는 유사한 방법을 만들었습니다. 나는 한 가지 방법이 아니라 최종 답을 얻을 수있는 모든 방법을 찾아야합니다. 어떻게해야합니까?

현재 역순으로 작업하면 항목이 최대 값에 추가 된 한 가지 방법 만 찾을 수 있습니다. 그러나 필자의 의견으로는 항목이 최대 값에 추가되는 2 가지 이상의 방법이있을 수 있습니다. 이 두 가지 이상의 방법을 알고 싶습니다. 그 이유는 몇 가지 기준에 따라 최적의 항목 세트를 선택해야하기 때문입니다. 어떻게해야합니까? DP 매트릭스 또는 아래 코드를 사용해야합니까?

입력

제약 :

maxWeight = 100

ID/값/중량

1/50/40 2/40/30

3/30/40

4/50/40

출력 : 제약 조건을 기반으로 1,2,3 또는 2,3,4가있을 수 있습니다.

둘 다 동일한 점수와 무게를 합산합니다. 세트를 모두 어떻게 확인할 수 있습니까?

서곡 : ArrayList에있는 항목의 시간 속성이 특정 한도 내에서 을 떨어지면 내가 결정하고

. 나는 내 배플 (bool) 배열 (wasTaken)을 만들었고 을 가져갈 수있는 요소를 넣어 두었다. 여기서는 행렬을 통과하여 어떤 요소가 찍혔는지 확인하고 나중에 을 입력 한 다음 나중에 (정렬 한 후) 인쇄 할 항목의 ID를 저장합니다. int [] [] sol below는 이전 방법의 동적 프로그래밍 스타일로 채워진 행렬을 나타냅니다. i 값은 항목을 나타내고 Weight는 고려중인 가중치를 나타냅니다. 이것은 this 링크와 비슷한 방식으로 방식으로 이루어졌습니다.

내 현재 코드 :

public static void findElements(boolean[][] wasTaken, int maxWeight, ArrayList<Nodes> items, int[][] sol, int currentTime, int limit) { 
     int K = maxWeight; 
     int n = items.size(); 
     int count = 0; 
     int[] forPrint = new int[n]; 
     for (int i = n-1; i>=0; i--) { 
      if (wasTaken[i][K] == true && (currentTime - items.get(i).time <= limit)) { 
       forPrint[i] = items.get(i).index; 
       count++; 
       K = K - items.get(i).height; 

      } 
     } 
     Arrays.sort(forPrint); 
     showResult(count, forPrint); 
    } 

Answer 1

는 1n-j를 들어, p[j]이 항목 j의 이익하고 w[j]는 무게가 될 수 있도록하자. n-0에서 j 및 0에서 W 무게 한계까지 들어 opt[j][W]이 W보다 크지 총 중량의 1..j에서 항목을 선택 최대 총 이익이 될 수 있습니다.컴퓨팅 opt, 우리는 우리가 반복적으로 작업하고 깊이 우선,

opt[j][W] = max(p[j] + opt[j - 1][W - w[j]], opt[j - 1][W]) if j > 0 and W ≥ 0, 
       ^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^ 
         item j chosen   item j not chosen 
      0             if j = 0 and W ≥ 0, 
      -infinity (i.e., infeasible)       if W < 0. 

모든 최적의 솔루션을 열거하려면 재발이있다. j과 W이 주어진 경우, 이것이 기본 항목 인 경우 선택한 항목의 현재 세트 (W ≥ 0 인 경우) 또는 전혀 표시되지 않는 경우 (W < 0 인 경우). 그렇지 않은 경우 opt[j][W]과 max. 첫 번째 인수와 동일하면 j - 1 및 W - w[j]의 모든 솔루션을 j 항목을 선택한 항목 집합에 추가합니다. opt[j][W]이 두 번째 인수와 같으면 j - 1 및 W에 대한 모든 솔루션을 산출합니다. 두 인수가 동일 할 수 있기 때문에 여러 솔루션을 얻을 수 있습니다.