• 유명한 knapsack problem 예제

  • 도둑이 박물관에 침입했다. 값비싼 그림들, 조각상들, 그리고 보석들이 널려있다. 도둑은 이러한 물건들의 가치를 잘 알고 있으며, 각각의 물건들은 뒷 거래상들에게 수백 혹은 수천 달러로 팔릴 것을 알고 있다. 하지만, 도둑은 강도 현장에 배낭을 딱 하나 가져왔고, 여기에 들어가는 것만 가져갈 수 있다. 도둑은 훔쳐갈 물건의 가치를 극대화하기 위해서 어떤 물건을 가져가야 할까?

    • 문제 해결을 위한 두 가지 방법이 있다.

      1. 0-1 knapsack problem
      • on & off; 넣을지 안넣을지.
      • Dynamic Programming(O), Greedy(X)
      2. Fractional knapsack problem
      • 물건들을 잘라서 일부분만 가지고 올 수 있는 경우.
      • DP(O), Greedy strategy(O)

    →둘 다 optimal-substructure가 있기 때문에 DP로 풀 수 있지만, fraction knapsack만 greedy로 풀 수 있다.

Fractional knapsack problem

• fractional problem을 풀기 위해서, 먼저 value per pound = vi/wi 를 계산한다.
• greedy strategy에 따라, 도둑은 value per pound가 가장 많은 item을 가져가는 것부터 시작한다.
• 만약 첫 번 째 item을 다 가져간 이후에도 배낭에 자리가 남았다면, 그 다음으로 가치가 큰 물건을 선택하는 과정을 반복하여 가방이 다 찰 때까지 진행한다.

0-1 Knapsack Problem

• maximum capacity: W
• n개의 item의 set: S
• 각각의 item은 weight wi, benefit value bi를 가진다.
• 모든 wi, bi, W는 integer value이다.

[1] brute forth approach

• straightforward 알고리즘으로 풀어보자

  • n개의 item이 있기 때문에 2^n개의 가능한 조합이 있다. (0-1 truth table)

    1. most total value
    • 전체 value가 가장 많은 것
    2. total weight less or equal to W
    • W보다 적거나 같은 weight
• Running time: theta(2^n)

→ 더 나은 방법이 있는가?

[2] Greedy approach → 0-1 knapsack문제에 대해서 풀 수 없음.

• fractional 한 경우에 대해서는 가능

[3] Dynamic programming

• subproblem을 올바르게 정의해야 함
• 만약, item들이 1..n으로 라벨링 되어 있다면, subproblem은 Sk = {items labeled 1, 2, ..., k}에 대한 optimal solution을 찾는 것이다.
  • valid subproblem definition이다.