동적 프로그래밍 - 부분 집합 합계 - 경로 재구성

Question

음수가 아닌 정수 집합과 값 합계가 주어지면 주어진 합계와 합이 같은 주어진 집합의 부분 집합이 있는지 결정합니다. 예를 들어

은 : 지금은 주어진 합을 형성하는 모든 가능한 조합을 재구성 할, 그러나

public boolean isSubsetSum(int[] set, int sum) { 
    Arrays.sort(set); 
    boolean[][] memo = new boolean[set.length+1][sum+1]; 
    for (int i = 0; i < memo.length; i++) { 
     memo[i][0] = true; 
    } 
    for (int i = 1; i < memo.length; i++) { 
     for (int j = 1; j < memo[i].length; j++) { 
      if (set[i-1] > j) { 
       memo[i][j] = memo[i-1][j]; 
      } else { 
       memo[i][j] = memo[i-1][j] || memo[i-1][j-set[i-1]]; 
      } 
     } 
    } 
    return memo[memo.length-1][memo[memo.length-1].length-1]; 
} 

:

set = {1,2,5,7} 
sum = 8 
=> true 

는 사실이 코드의 문제를 해결했다.

내 메모 매트릭스에서 그렇게 할 수 있습니까, 아니면 다르게해야합니까?

Answer 1

take[i][j]이라는 새 DP 테이블을 부울로 만듭니다. 부분 집합 합계 j에 대해 i-th 요소를 사용하면 사실입니다. 당신은 당신의 일반 메모 테이블과 동시에 그것을 채우기 :

마지막으로

for (int i = 1; i < memo.length; i++) { 
    for (int j = 1; j < memo[i].length; j++) { 
     if (memo[i-1][j]){ 
      //no need to take ith elements, first i-1 have sum j 
      take[i][j] = false; 
      memo[i][j] = true; 
     } 
     else if (j-set[i-1] >= 0 && memo[i-1][j-set[i-1]){ 
      //take ith element, and search for set of size j-set[i-1] in 1..i-1 
      take[i][j] = true; 
      memo[i][j] = true; 
     } 
     else{ 
      //neither memo[i-1][j] or memo[i-1][j-set[i-1]] valid, so no way to make sum 
      take[i][j]=false; 
      memo[i][j]=false; 
     } 

    } 
} 

가하는 솔루션을 재구성, 당신은 시작 : 당신은 솔루션의 모든 설정이 일반화 할 수

i=set.length 
j=sum 
while (i>=0 && j>=0){ 
    if (take[i][j]){ 
    print(set[i]) 
    j = j - set[i] 
    i=i-1 
    } 
    else{ 
    i=i-1 
    } 
} 

.