[BOJ] 평범한 배낭 in Python

문제풀러 가기!

대표적인 냅색 알고리즘 문제였습니다. 물론 전 처음에는 못풀었어요. dfs로 접근했다가 시간 초과 났습니다. 안그래도 코드 짜면서도 좀 그랬습니다. 입력값이 많은데, 이래도 되는건가... 라는 생각들이 많았습니다. 아직 완전히 냅색 알고리즘을 이해하진 않았지만, 제가 이해한 냅색은 다음과 같습니다.

최대 value를 찾기 위해서 특정 weight의 value와 그 weight을 제외한 전의 value를 계속 비교하면서 업데이트 하는 dp 풀이가 존재했습니다.

아래는 처음에 풀이했던 dfs 풀이입니다.

# 이건 틀린 코드입니다.
import sys

n, k = map(int, sys.stdin.readline().strip().split())

w_list = []
v_list = []

for _ in range(n):
    w, v = map(int, sys.stdin.readline().strip().split())
    w_list.append(w)
    v_list.append(v)


visited = [False for _ in range(n)]
answer = 0

def dfs(weight, value):
    global answer


    if weight > k:
        return
    else:
        answer = max(answer, value)

    for i in range(n):
        if not visited[i]:
            visited[i] = True
            dfs(weight + w_list[i], value + v_list[i])
            visited[i] = False

dfs(0, 0)
print(answer)

아래는 dp 풀이입니다.

import sys

n, k = map(int, sys.stdin.readline().strip().split())

init = [[0, 0]]
knapsack = [[0 for _ in range(k+1)] for _ in range(n+1)]

for _ in range(n):
    init.append(list(map(int, sys.stdin.readline().strip().split())))

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

        if j < w:
            knapsack[i][j] = knapsack[i-1][j]
        else:
            knapsack[i][j] = max(v + knapsack[i-1][j-w], knapsack[i-1][j])

print(knapsack[n][k])