개발 공부 - [동적계획법 (Dynamic Programming)] Dynamic Programming - 6

Knapsack Problem

Knapsack

- n개의 아이템과 배낭

- 각각의 아이템은 무게 wi와 가격 vi를 가짐

- 배낭의 용량 W

- 목적: 배낭의 용량을 초과하지 않으면서 가격이 최대가 되는 부분집합

- 예:

    {1,2,5}는 가격의 합이 35

    {3,4}는 가격의 합이 40

    {3,5}는 46이지만 배낭의 용량을 초과함

i                vi                wi

1                1                1

2                6                2

3                18              5

4                22              6

5                28              7

knapsack instance

(weight limit W = 11)

Greedy

    - 가격이 높은 것 부터 선택

    - 무게가 가벼운 것부터 선택

    - 단위 무게당 가격이 높은것 부터 선택

i                vi                wi

1                1                1

2                6                2

3                18              5

4                22              6

5                28              7

knapsack instance

(weight limit W = 11)

순환식

- OPT(i) : 아이템 1,2,...,i로 얻을 수 있는 최대 이득

- 경우 1: 아이템 i를 선택하지 않는 경우

        OPT(i) = OPT(i-1)

- 경우 2: 아이템 i를 선택하는 경우

        OPT(i) = ?

순환식

    - OPT(i, w) : 배낭 용량이 w일 때 아이템 1,2,...,i로 얻을 수 있는 최대 이득

    - 경우 1: 아이템 i를 선택하지 않는 경우

        OPT(i, w) = OPT(i-1, w)

    - 경우 2: 아이템 i를 선택하는 경우

        OPT(i) = vi + OPT(i-1, w-wi)

    OPT(i,w) = 

                    0                                                           if i =0

                    OPT(i-1, w)                                              if wi>w

                    max{OPT(i-1, w), vi + OPT(i-1, w-wi)}             otherwise

Bottom-Up

KNAPSACK(n, W, w1, ..., wn, v1, ..., vn)

FOR w = 0 TO W

    M[0,w] <- 0

FOR i = 1 to n

    FOR w = 1 to W

    IF (w1 > w)

        M[i,w] <- M[i-1 , w].

    ELSE

        M[i,2] <- max {M[i-1,w], vi + M[i-1, w-wi]}.

RETURN M[n,W]

시간복잡도

    - 시간복잡도 O(nW)

    - 다항시간인가?