백준 12865 평범한 배낭 (파이썬)

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

 

정답 코드

import sys
def knapsack(N, capacity):
    for i in range(1, N+1):
        W = weight[i-1]
        V = value[i-1]
        for j in range(1, capacity+1):
            if W > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(V+dp[i-1][j-W], dp[i-1][j])
    return dp[N][capacity]

if __name__=="__main__":
    input = sys.stdin.readline
    N, K = map(int, input().split())
    #행은 아이템의 개수
    #열은 가방의 최대 무대
    #dp[i][j] : i개의 아이템을 골랐을 때 j 무게에서의 최대의 가치
    dp = [[0] * (K + 1) for _ in range(N+1)]
    weight = []
    value = []
    for i in range(N):
        W, V = map(int, input().split())
        weight.append(W)
        value.append(V)

    print(knapsack(N, K))

 

정리 및 복습 

dp를 2차원 리스트로 선언,

i = 아이템의 개수

j = 가방이 허용할 수 있는 최대 무게

dp[i][j] = i개의 아이템을 골랐을 때 허용가능 한 무게(j)에서의 최대 가치

만약 현재 무게가 허용 가능한 배낭의 무게(j)

 

 

2년전 알고리즘 수업 때 배웠던 내용이 다시 생각나네요

위 문제는 knapsack 문제로 배낭 문제 및 DP 문제 중 가장 유명한 문제입니다.

분리 가능한 knapsack 문제라면 그리디로 풀어야하지만 이 문제는 분리가 불가능한 0-1 knapsack 문제라서 DP로 풀어야합니다.

 

저는 처음에 리스트의 높이를 물건 무게의 최대값으로 설정하고

max(V+dp[i-1][j-W], dp[i][j-1]) 

dp[i][j] = dp[i][j-1]

로 잘못 설정해서 틀렸습니다.

 

dp[i]를 구할 때, 이전 무게와 비교하는 것이 아니라 현재 i에서 1을 뺀 이전 개수 dp 값인 dp[i-1]값과 비교해야 하는 것을 다시 깨달았습니다.