알고리즘 분류

  • 동적 프로그래밍

0-1 KN 문제 정의

$n$ : 아이템의 개수

$w_i$ : $i$ 번째 아이템의 무게

$p_i$ : $i$ 번째 아이템의 이익

$W$ : 가방에 넣을 수 있는 최대 무게

$D[i][w]$ : 최대 무게가 $w(0<w\leq W)$일 때, i까지 넣었을 때 최대 이익

$D[n-1][W]$ : $W$만큼 담을 수 있는 가방에, n개의 아이템을 넣었을 때 최대 이익

0-1 KN 문제 점화식

$i$ 번째 아이템을 가방에 넣을 수 있는가?

  • 넣을 수 있는 경우 $(w_i \leq w)$

    $$
    D[i][w] = max(D[i-1][w-w_i] + p_i,\ D[i-1][w])
    $$

    • ‘넣는다’ $(D[i-1][w-w_i] + p_i)$
    • ‘넣지 않는다’ $(D[i-1][w])$
    • 두개의 경우 중 이익이 큰 방향으로 선택한다.

  • 넣을 수 없는 경우 (넣지 않는다)

    $$
    D[i][w] = D[i-1][w]
    $$

0-1 KN 타뷸레이션

https://i.ibb.co/yX9r3L5/2022-02-19-6-29-36.png

0-1 KN 관련 문제

백준 12865번 - 평범한 배낭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
N, W = map(int, input().split())
weights = [0] *N
profits = [0]* N
D = [[0] * (W + 1) for __ in range(N)]

for i in range(N):
    w, p = map(int, input().split())
    weights[i] = w
    profits[i] = p

for i in range(N):
    for w in range(0, W + 1):
        if weights[i] <= w:
            D[i][w] = max(D[i-1][w-weights[i]] + profits[i], D[i-1][w])
        else:
            D[i][w] = D[i-1][w]

print(D[N-1][W])