Best-FS 0-1 Knapsack Problem

전략 설계

넓이 우선 탐색처럼 같은 level의 노드를 모두 탐색하는데,

queue에 있는 노드 중 bound가 큰 애를 먼저 뺀다.

⇒bound가 높은 것이 max_profit을 더 많이, 빨리 갱신할 것이라고 생각하는 것

가능성 있는 애들만 선택한다고 볼 수 있음

자료구조: Heap

우선순위 큐를 사용한다. ⇒ 우선 순위의 기준은 bound의 크기

“가는 데 순서 없다.”_ Ji woong Choi.

Pseudo code

struct node {
  int level;
  int profit;
  int weight;
  float bound;
}

void knapsack3(int n, const int p[], cont int w[], int W, int &maxprofit) {
  queue_of_node PQ;
  node u, v;
  initialize(PQ);
  v.level = 0;
  v.profit = 0;
  v.weight = 0;
  v.bound = bound(v);
  maxprofit = 0;
  insert(PQ, v);
  while (!empty(PQ)) {         // Remove nod with
		remove(PQ, v); // best bound 
    if (v.bound > maxprofit) { // Check if node is still
      u.level = v.level + 1;   // promising.
      u.profit = v.profit + p[u.level];
      u.weight = v.weight + w[u.level];
      if ((u.weight <= W) && (u.profit > maxprofit))
        maxprofit = u.profit;
      u.bound = bound(u);
      if (bound(u) > maxprofit)
        insert(PQ, u);
      u.weight = v.weight; // Set u to the child
      u.profit = v.profit; // that does not include
      u.bound = bound(u);  // the next item.
      if (u.bound > maxprofit)
        insert(PQ, u);
    }
  }
}

bound/우선순위 큐/나올 때 들어갈 때 유망함 판단

들어갈 땐 나도 나름 유망했는데,,,

넣을 땐 유망했던 노드가, 알고리즘을 진행하다 보면 나오면 쓸모 없을 때가 있다.

예를 들어, max_profit이 50일 때, bound가 100인 node A를 queue에 넣었다고 하자.

queue에서는 bound가 160, 150가 있기 때문에, 걔들이 먼저 나갈 것이다.

그때, max_profit이 110이 되었다고 하자. ⇒ 갱신

A가 queue에서 나오면, 쓸모가 없어진 것이다.

이런 경우에 대비해서, if문을 이용하여 max_profit<bound가 아닐 경우

자식 노드를 방문 하지 않아야 한다.

⇒ 즉, queue에 넣은 것은 그 노드 자체를 방문하기 위해서 넣은 것이 아니라

그 노드의 자식을 방문하기 위해서 넣은 것이다.

queue에서 나온 다음 바로 자식을 방문하는 것이 아니라, queue에서 빼고 유망한지 한번 더 검사한다.

정리하고 보니 당연한 이야긴데 교수님 왜 이렇게 열심히 설명하신거에요

당연한 이야기 아니고 중요한거엿나봄

BFS는 이런거 없음!! 손계산하다가 헷갈리지 말기

작동 원리