[DP] 부분집합의 합

 

 

 

 

n번째까지 고려했을 때 합이 m인 부분집합이 존재하는가?

 

합이 0인 것은 공집합이다.

•  이전에 만든 값이 이미 원하는 합을 만들어놨는가? -> 그렇다면 만들 수 있으므로 true
•  아니면 이번에 새로 추가를 하면 원하는 합이 만들어지는가? 현재 원하는 합에서 새로 추가한 값을 뺀 경우가 만들어져 있는가? -> 그렇다면 만들 수 있으므로 true

 

optimal substructure를 갖고 있으므로 새로 추가된 값에 대해서만 고려한다.

작은 부분에 대해서는 이미 다 구했다고 가정한다.

 

부분집합을 찾고자 한다면 n번째까지 고려했을 때 가능한지 생각해봐야한다.

 

 

[동적 프로그래밍 예제] 부분집합의 합(C언어)