[Algorithm] subset sum problem in dynamic programming

 

subset은 한국말로 '부분집합'이라는 뜻이고, subset sum problem은 따라서 부분집합 더하기 문제?라고 생각할 수 있다!!

 

subset sum problem이 어떤거냐면, 

 

total = 11이고 

{2, 3, 7, 8, 10}인 집합이 있으면, 

 

집합의 원소들을 더해서 total값을 만들 수 있는지 확인하는 문제이다. 

 

 

세로줄에는 각각 원소들, 가로줄에는 0부터 total까지가 배치되어 있다고 해 보자. 

 

2, 3, 7, 8, 10을 0개씩 쓰면 합이 0이 될 수 있으므로 첫 줄을 다 T로 채워준다. 

 

1은 2의 합으로 될 수 없으므로 F. 

 

2는 2의 합으로 될 수 있으므로 T. 

 

3 이상의 값은 2로 만들어질 수 없으므로 전부다 F. 

 

3보다 작은 값은 !!!윗줄을 그대로 채워준다

 

 

 

3은 T

 

이제 4부터가 중요한데,

일단 바로 윗줄이 true이면 true를 써준다. 

만약 false라면, 

T[윗줄][4-rowValue]을 봐서, true이면 true를 써준다. 

그것도 아니라면 false가 된다. 

 

4는 윗줄도 false, T[0][1]도 false여서 false. 

 

 

5는 윗줄은 false이지만 T[0][2]가 true여서 true. 

 

나머지는 false. 

 

남은 칸들도 위와 같은 방식으로 채워준다. 

 

 

코드는, 

 

if (j<input[i])

    T[i][j] = T[i-1][j] // 윗줄이 1이면 그대로 가져온다. 

else 

    T[i][j] = T[i-1][j] || T[i-1][j-input[i]] // T[i-1][j-input[i]]도 F이면 false.