[Python] 평범한 배낭 - 백준 (DP)

해당 글은 백준 12865번 문제 '평범한 배낭'을 다룬다.

문제

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

12865번: 평범한 배낭

 

설명

전형적인 0-1 Kanpsack Problem 문제로, 물건이 나누어 질 수 없을때의 배낭문제이다.

행은 물건의 갯수, 열은 담을 수 있는 무게로 knapsack 행렬을 만들고, 행을 순서대로 돌아가면서 배열을 채워가며 만들어준다.

-현재 물건이 행렬의 돌고있는 무게보다 작다면, kanpsack[i-1][j]를 입력해준다.

-작지않다면, value+knapsack[i-1][j-weight]과 kanpsack[i-1][j] 중 최댓값을 입력해준다.

k무게일 때의 최댓값은 knapsack[n][k] 이다.

 

코드

n, k = map(int, input().split())
data = [[0,0]]
for i in range(n):
    data.append(list(map(int, input().split())))

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

for i in range(1, n+1):
    for j in range(1, k+1):
        weight = data[i][0]
        value = data[i][1]

        if j < weight:
            knapsack[i][j] = knapsack[i-1][j]
        else:
            knapsack[i][j] = max(value+knapsack[i-1][j-weight], knapsack[i-1][j])
print(knapsack[n][k])