분기 한정법

Branch : 이전 상태 공간 트리에서 다음 가지로 넘어가는 경우를 말함
Bound : 한계
이전의 백 트레킹과 크게 다르지 않다.
그 부분 집합의 합을 구하는 문제와 크게 다르지는 않다.
결국 특정 노드를 방문했을 때, 이후를 쭉 봤을 때, 이놈이 갈수 있는 최대치? 혹은 최소치가 기대가 되면 가고 애초에 글렀으면 안가는 것
이전과 다른점은, 해당 노드의 값을 기준으로 판단하는 것이 아니고
더 나아가서 이 값을 기준으로 나머지 값의 한계 Bound를 찾고 이를 기준으로 판단한다는 것이다.
결국 포텐셜을 본다는 것(… 에혀)

0-1 배낭 채우기 문제

자 다시 돌아왔다.
W의 무게를 담을 수 있는 가방이 있을 때
가치 pi, 각각의 무게 wi가 있는 물건 n개가 있다면
가장 가치를 높히면서 가방에 담을 때의 물건 리스트는?

상태 공간 트리

자 얘를 간단하게 생각해보면 이런 상태공간 트리가 생긴다.
물건이 n개라면 2^n개의 말단 노드가 생기는 거지.
그리고 거기서 꼭 판단을 해야해
이전에는 이런 접근도 했었어.
동적 계획법을 사용해서, i번째까지의 물건을 고려했을 때, w의 무게를 넘지 않는 최대 가치라고 정의를 하고
그럼 그 상태에서 i번째 물건을 넣었을 때의 가치와 넣지 않았을 때 가치를 비교해서 업데이트를 하는 거지.
하지만 이 방법 역시 마지막 값을 구하기 위해 2개의 비교가 필요했고,
결국 물건이 n개인 경우 2^n 정도의 시간 복잡도가 발생했지.

Branch and bounds : DFS

branch and bound를 사용

자, 그럼 이번에는 이렇게 해보자.
내가 특정 노드를 방문했을 때, 이후로 가질 수 있는 최대 가치를 알 수 있다고 생각해보자.
그럼 내가 지금까지 얻은 가치보다, 얻을 수 있는 최대 가치가 더 크대,
돈 여기다가 투자하면 지금 번거보다 20%더 번대
그러면 투자 하잖아.
똑같이 그런 경우에는 탐색을 진행하는 거야.
그런데 얘가 최대 가치를 계산해봤자 안돼
그러면 내가 투자를 왜해.
이런 느낌이야.
그럼 이걸 어떻게 구할지를 생각해보자.
- 일단 무게당 가치가 높은게 먼저 오는게 맞아보이니, 이 순서로 정렬해둔 상태로 시작해보자.
- profit : i번째 노드까지 방문했을 때, 이때까지 넣은 아이템의 가치 합
- weight : i번째 노드까지 방문했을 때, 이때까지 넣은 아이템의 무게 합
- bound : 이 이후로 얻을 수 있는 최대 가치 (물건 잘라서 넣을 수 있다고 하자)
- 이 bound를 구하려면, 몇번째 물건을 넣었을 때 W를 넘는지를 알아야해
- 예를 들어 6번째 물건까지 넣으니까 W를 넘어가, 그럼 최대 가치를 구하려면 6번째 원소는 빼고
- 나머지를 다 넣어서 가치를 계산한 다음에 6번째는 잘라서 가치를 계산해서 더해줘야 최대 가치가 나오잖아(이론적)
- 그 6이라는 숫자를 k라고 해보자. 그러면 i번째 이후부터 k전까지 다 더해줘야겠지?
- 그러니까
- bound = profit + $\sum_{j=i+1}^{k-1}p_j$ + (W-totalweight) * pk/wk
- 여기서 total weight는 k-1번째까지의 무게를 다더한 값이야.
- 자 그러면 탐색을 하면서, 지금까지 최대 가치를 담을 변수 maxprofit 하나를 잡아주자.
- maxprofit >= bound이면 탐색할 필요가 없다.
  - 같아도 그러한 이유는 bound는 정말 이론적 최선이기 때문이지.