[백준 알고리즘] 12865번 평범한 배낭. 파이썬(python)/냅색 knapsack

냅색 알고리즘

배낭의 무게가 제한되어 있을 때 최대 가치가 되도록 물건을 선택하는 문제

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

12865번: 평범한 배낭

무게가 커서 담을 수 없다. => 이전 물건을 유지한다.

if j<w이면 dp[i][j]=dp[i-1][j]

 

물건을 넣을 수 있다. => 현재 물건을 넣지 않는다 OR 현재 물건을 담고 여분의 무게의 물건도 담는다.
dp[i][j]=max(dp[i-1][j], dp[i-1][j-w]+v)

예시)

위의 그림에서 배낭에 7kg을 담는데 현재 3kg을 담으려고 한다.(빨간 부분)

1. 3kg 물건을 담지 않는다. -> 가중치가 dp[i-1][j]가 된다 (노란색)

2. 3kg 물건을 담고 남은 4kg를 담는다 -> (3kg의 가중치 6)+(4kg으로 담을 수 있는 최대 가중치 8)=14(파란색)

 

import sys
input=sys.stdin.readline

n, k = map(int, input().split())
thing = [[0,0]]

for i in range(n):
    thing.append(list(map(int, input().split())))

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

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

        if j<w: # 현재 배낭에 넣을 수 있는 무게 < 물건의 무게 (넣을 수 없을 때)
            dp[i][j]=dp[i-1][j] # 이전 개수의 물건을 유지한다
        else: # 물건을 넣을 수 있을 때
            dp[i][j]=max(dp[i-1][j], dp[i-1][j-w]+v) # 물건을 넣지 않을지 or 여분의 무게의 물건을 담는다 했을 때의 가중치 + 현재 가중치 

print(dp[-1][-1])