[파이썬]백준 12865 평범한배낭

링크

백준 12865 평범한배낭

DP유형의 유명한 문제인 knapsack문제이다.
문제 이름은 평범한배낭이나 DP가 너무 어려운 나에겐 매우매우 안평범한 배낭이었다.

담는 물건을 행, 배낭의 크기를 열로 하는 2차원 memo를 만든다.
물건을 하나 선택해서, 배낭의 크기를 하나씩 키워가며 배낭의 크기마다 담을 수 있는 물건의 최대 가치를 memo에 적는다.

가방의 크기보다 물건의 무게가 클 경우는 (else) 물건을 담지 못하므로 해당 물건을 담기 전의 가치를 그대로 적어준다.

가방의 크기가 물건을 담을 수 있는 경우는 (if bag_size >= weight) 해당물건을 담거나 담지 않았을때의 가치를 비교해주면 된다.

해당 물건을 담지 않을 경우엔 이전의 가치를 그대로 적고

해당 물건을 담을 경우엔 물건의 무게만큼의 공간을 배낭에서 확보했을 때의 가치 (memo[item-1][bag_size - weight]) 에 담을 물건의 가치를 더해준다.

그 후 이 둘을 비교해 큰 값을 적는다.

혼자 풀 수가 없어 다른사람의 코드를 참고했는데도 이해하는데 한참걸렸다.

처음에 혼자 풀 땐 물건의 무게를 중심으로 물건 여러개의 무게가 배낭의 최대 무게안일경우 해당 가치를 적어줬는데, 이 경우 최대가치를 제대로 찾지 못했다.

배낭의 크기를 중심으로 물건을 넣었다 뺏다 하는 식으로 구현하니 풀 수있었다.

정답 코드

import sys; input = sys.stdin.readline

def dp(bag):
    for item in range(1, N + 1): # 물건하나씩 꺼내서 가방에 넣어봄
        weight, value = bag.pop()
        for bag_size in range(1, K + 1): # 배낭의 크기를 최대까지 키워가며 담으며 가치를 적음
            # 물건을 담을만큼 가방이 커지면
            if bag_size >= weight:
                # 물건을 안담았을 때 가치와, 담았을 때의 가치 중 큰것을 취함
                memo[item][bag_size] = max(memo[item-1][bag_size], memo[item-1][bag_size - weight] + value)
            else: # 물건의 무게가 배낭의 크기보다 작을 경우
                memo[item][bag_size] = memo[item - 1][bag_size] # 물건 못담음 즉, 가치추가 X

N, K = map(int, input().split())
# 선택0, 무게0의 경우를 만들기 위해 각각 +1씩
memo = [([0] * (K + 1)) for _ in range(N + 1)]
bag = []
for _ in range(N):
    w, v = map(int, input().split())
    bag.append([w, v])
dp(bag)

print(memo[N][K])

알게된 것👨‍💻

• DP는어려워