백준 12865 배낭 파이썬 문제풀이 (python 최적화, 재귀, 백트래킹 경우의 수, 기억, 탑다운 DP, 메모이제이션)

문제 보러가기

 

백준 배낭 파이썬 문제풀이

N개 물건 중 배낭에 특정 무게 K까지 담을 수 있고, 

제한된 무게 내에서 최대한의 가치를 갖도록 물건들을 담는 문제이다.

 

재귀함수를 이용해서 각 물건을 넣는 경우와 안넣는 경우를 분리해서 뻗어나간다.

 

n,k = map(int,input().split())
answer = 0
stuff = []
def recur(idx, wgt, val):
    global answer

    # 무게가 넘으면
    if wgt > k:
        return
    if idx == n:
        answer = max(answer, val)
        return
    recur(idx+1, wgt+stuff[idx][0], val+stuff[idx][1])
    recur(idx+1, wgt, val)

for i in range(n):
    w,v = map(int,input().split())
    stuff.append([w,v])
recur(0,0,0)
print(answer)

이렇게 재귀함수를 이용해서 

무게가 넘는 경우는 무시하고, 최대 가치를 얻도록 했다. 

시간초과라니.. 

 

아무래도 재귀로는 시간이 안되니, DP로 풀어야할 것 같다.

 

DP로 접근하기 

n,k = map(int,input().split())
stuff = []
def recur(idx, wgt):
    global answer

    # 무게가 넘으면
    if wgt > k:
        return float("-inf")
    if idx == n:
        return 0

    dp[idx] = max(
        recur(idx + 1, wgt + stuff[idx][0]) + stuff[idx][1],
        recur(idx + 1, wgt)
    )
    return dp[idx]

for i in range(n):
    w,v = map(int,input().split())
    stuff.append([w,v])

dp = [-1 for _ in range(n+1)]
recur(0,0)
print(max(dp))

dp 배열을 만들고 무게가 넘는 경우는 제외하고,

dp에 다음 순서 물건들의 재귀 함수를 진행한 최댓값을 담는다.

하지만 틀렸다.. 뭐가 문제지? 

 

2차원 DP

무게를 위해서 2차원 배열로 dp를 변경해보자.

n,k = map(int,input().split())
stuff = []
def recur(idx, wgt):
    global answer

    # 무게가 넘으면
    if wgt > k:
        return float("-inf")
    if idx == n:
        return 0
    if dp[idx][wgt] != -1:
        return dp[idx][wgt]

    dp[idx][wgt] = max(
        recur(idx + 1, wgt + stuff[idx][0]) + stuff[idx][1],
        recur(idx + 1, wgt)
    )
    return dp[idx][wgt]

for i in range(n):
    w,v = map(int,input().split())
    stuff.append([w,v])

dp = [[-1 for _ in range(100_001)] for _ in range(n)]
recur(0,0)
print(max(max(row) for row in dp))

dp 자체만 2차원으로 변경하고 wgt를 두 번째 index로 사용한다.

다른 것은 크게 변하지않았다.

 

이게 어떤 효과를 주는가. 

경우의 수가 물건만이 아니라 무게도 고려하기 때문에 차원이 하나 늘어난 것이다.

 

이에 따라 원래는 각 케이스를 하나씩 고려해서 재귀를 도느라 시간이 오래 걸리지만,

dp에 무게가 추가되면서 이미 구한 무게의 케이스에 대해서는 또 연산하지 않아 시간이 줄어든다.

해결했다. 

2차원 DP에 대해서 잘 알아가자.