[Baekjoon] 평범한 배낭(python)

https://www.acmicpc.net/problem/12865

문제 접근

처음 이 문제를 봤을 때는 BackTracking을 이용해 해당 물건을 넣는 경우와 안 넣는 경우를 모두 구하려고 시도했다. 그렇게 되면 시간 복잡도가 O(2^N)이 되므로 최대 2^100번 연산을 해야 하므로 시간 초과가 날 수 밖에 없었다.

검색을 통해 이 문제는 다이나믹 프로그래밍을 통해 해결해야 했고 Knapsack 문제라고 불리는 아주 유명한 문제였다.

---

풀이 과정

N은 물품의 수이고 K는 배낭 무게이다. 물건을 하나씩 넣는 경우와 안 넣는 경우를 배열에 저장하면서 처리하면 된다. 그렇게 되면 O(NK)이 되고 최대 연산량은 10,000,000이므로 제한 시간을 통과할 수 있다.

 

DP 점화식을 표현하면,

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)

 

dp[N][K]	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1	0	0	0	0	0	13	13
2	0	0	0	8	8	13	13
3	0	0	6	8	8	13	14
4	0	0	6	8	12	13	14

 

N = 1, W = 6, V = 13

 

1번 물건의 무게는 6이므로 dp[1][6]와 dp[1][7]이 13이 된다.

 

N = 2, W = 4, V = 8

 

2번 물건을 넣는 경우는 가치가 8이 된다.

dp[2][6]은 dp[1][6]이 dp[1][2] + 8보다 크기 때문에 13이 된다.

이런 경우는 2번 물건을 넣는 경우보다 넣지 않는 것이 더 큰 가치를 가질 수 있다는 의미가 된다.

 

N = 3, W = 3, V = 6

 

dp[3][7]은 dp[2][7]이 13이고 dp[2][4] + 6이 14기 때문에 14가 된다. 즉 3번 물건을 넣게 되면 가치가 더 크게 된다.

 

N = 4, W = 5, V = 12

 

위에서 했던 것과 마찬가지로 dp배열을 채우면 된다.

 

최종적으로 만들어지는 배열은 위의 표와 같아진다. 

우리가 구하고자 하는 값은 dp[4][7]에 저장되므로 해당 값을 출력해주면 답이 된다.

---

정답 코드

import sys


def solution():
    for i in range(1, n + 1):
        for j in range(1, k + 1):
            w, v = items[i][0], items[i][1]

            if j < w:
                dp[i][j] = dp[i - 1][j]
                continue

            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)

    print(dp[n][k])


n, k = list(map(int, sys.stdin.readline().split()))
items = [[0, 0]]

for _ in range(n):
    w, v = list(map(int, sys.stdin.readline().split()))
    items.append([w, v])

dp = [[0] * (k + 1) for _ in range(n + 1)]

solution()