Sum of subset 알고리즘

소개

sum of subset알고리즘 관련된 연습문제의 풀이입니다.
sum of subset 관련 13번과 15번, 17번 문제 풀이입니다.
과제점수도 A로
실제로 풀때 약간 막히는 부분은 참고하시기 바랍니다.

목차

없음

본문내용

가장 먼저 Backtracking algorithm의 순서는 오름차순으로 정렬을 하는 것이다. 13번 문제에서 주어진 Weight들은 이미 정렬되어 있으므로 이 과정은 생략한다.
다음으로 상태공간트리를 생각해보면, 각각의 weight는 포함이 되느냐? 되지 않느냐? 라는 두가지 경우의 수를 가지고 있다. 따라서 각 노드의 자식들은 두 개씩 보유하게 된다. 이를 그림으로 나타내면 [그림 1]과 같다.

[그림 1] Sum of Subset의 상태공간트리

그리고 이후에 Promising의 조건을 확인해야된다. Sum of Subset의 Promising 조건은 다음과 같다.

<중 략>

[표 1]의 1번문항이 빠진 이유를 설명하자면, 정렬이 되어있지 않았을 경우, i+1번째의 Weight를 초과한다고 할때, 그 이후의 Weight가 항상 i+1보다 크지는 않다. 예를 들어서, i가 3일때 Weight가 10이고 W=12에 맞추고자 할때, W4 = 5라고 그다음 노드들이 Promising이 아니라는 것은 아니다. 즉, W6이 2라서 답인 경우도 존재할수 있기 때문이다. 즉 이 1번문항으로 Promising한지 아닌지는 판단이 불가능하다.

참고자료

· 없음