[ BOJ 12865 ] 평범한 배낭(Python)

문제

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

냅색 알고리즘 문제의 정석
n개의 물건,,k 무게까지 버티는 가방,, 최대 가치,,

문제 풀이

0. 입력 받기

for _ in range(n):
    row = tuple(map(int,input().rstrip().rsplit()))
    bag.append(row)

1. dp 배열 정의하기

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

dp[i][j] = 물건 무게의 합이 j일때, 처음 i개의 아이템 중 담을 수 있는 최대 가치

2. 현재 물건을 담았을 때 vs 담지 않았을 때 비교하기

# 현재 물건의 무게 w, 현재 물건의 가치 v
w = bag[i][0] 
v = bag[i][1]

# 물건을 담을 수 있을 때
if j >= w:
    # (현재 물건을 담지 않았을 때 갖는 최댓값 vs 현재 물건을 담았을 때 갖는 최댓값)
    dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v
else:
    dp[i][j] = dp[i-1][j]

코드

import sys
input = sys.stdin.readline

n,k = map(int,input().rstrip().rsplit())
bag = ['dummy']

# dp[i][j] = 물건 무게의 합이 j일때, 처음 i개의 아이템 중 담을 수 있는 최대 가치
# ( j = 1 ~ k )

# j가 현재 물건의 무게 w보다 작을때 : w를 담을 수 없으므로 전의 값을 복사한다.
# dp[i][j] = dp[i-1][j]

# j가 현재 물건의 무게 w와 같거나 클 때 : 물건을 담았을 때와 담지 않았을 때 max 값을 찾아준다.
# dp[i][j] = max( dp[i-1][j] , dp[i-1][j-w] + v)

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

for _ in range(n):
    row = tuple(map(int,input().rstrip().rsplit()))
    bag.append(row)

for i in range(1,n+1):
    for j in range(1, k+1):
        # 현재 물건의 무게 w, 현재 물건의 가치 v
        w = bag[i][0] 
        v = bag[i][1]

        # 물건을 담을 수 있을 때
        if j >= w:
            # (현재 물건을 담지 않았을 때 갖는 최댓값 vs 현재 물건을 담았을 때 갖는 최댓값)
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
        else:
            dp[i][j] = dp[i-1][j]

print(dp[n][k])