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

문제

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

제발,, 가방,, 들고가지 말아주라,,,
택배로 짐 부쳐주라..,.
hoxy 냅색 알고리즘을 모르신다면,, 함 읽어보세요~! (🔗 링크)

냅색 알고리즘

냅색 알고리즘은 유명한 dp 문제 중 하나이다.

한마디로 가방에 물건을 최대치로 담고, 최대의 가치를 구하면 된다.
이때 ⭐️ 특정 물건을 담지 않을 때, 최선의 값이 나올 수 있다는 점을 고려해야 한다.

문제 풀이

가방에 k kg 까지 담을 수 있고, 아이템의 개수는 n개 이다.
우선 dp 배열을 만들어줬다.

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

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

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

현재 물건의 무게가 w, 현재 물건의 가치가 v일 때,
j보다 w가 큰 경우에는 가방에 물건을 담을 수 없다.

그럴 땐 dp[i][j]에 이전 값 dp[i-1][j]를 그대로 담아준다.

만약 j가 w보다 같거나 클 땐, 물건을 담을 수 있다.
하지만 현재 물건을 담지 않았을 때와 담았을 때 가치를 비교해준 뒤 더 큰 값을 넣어줘야 한다.

[현재 물건을 담았을 때 가치]

dp[i][j] = dp[i-1][j-w] + v
# dp[i-1][j-w] : 현재 물건을 담기 직전, 갖고 있던 최대 가치
# v : 현재 물건의 가치

[현재 물건을 담지 않았을 때 가치]

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

코드

import sys
input = sys.stdin.readline

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

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])