[백준] 평범한 배낭

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

12865번: 평범한 배낭

 

동적 계획법 문제로 dp 배열을 잘 정의해주자.

 

dp 는 2차원 배열로 행을 물건의 개수, 열을 배낭의 무게로 잡는다.

dp[i][j] 는 물건이 i 개 있을 때 j 를 수용할 수 있는 배낭에 들어갈 수 있는 가치의 합의 최댓값이라고 정의하자.

 

그럼, 물건이 추가됐을 때, 그 물건의 무게가 j 보다 작으면 그 물건은 수용할 수 없으므로

dp[i][j] = dp[i-1][j] 즉, dp[i][j] 를 물건의 수용 여부가 판단 되기 전의 가치의 합의 최댓값이라고 설정한다.

 

반대로, 그 물건의 무게가 j 보다 같거나 크면 그 물건은 어떤 경우에는 수용할 수 있는 경우이므로

1) 수용하지 않았을 때의 가치의 합의 최댓값 : dp[i-1][j]

2) 수용했을 때의 가치의 합의 최댓값 : dp[i-w][j](그 물건을 수용하기 전의 가치의 합의 최댓값) + v

1), 2) 중 최댓값으로 설정한다.

 

우리가 구하고자 하는 i = N, j = K 인 경우의 dp 배열의 값을 정하고 반환하면 된다. 

 

import sys

N, K = map(int, sys.stdin.readline().split())
WV = [] 
dp = [[0] * (K + 1) for i in range(N + 1)]   

for i in range(N):
    WV.append(list(map(int, sys.stdin.readline().split())))
    
for i in range(1, N+1):
    w, v = WV[i-1]
    
    for j in range(1, K+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)

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

 

1차원 dp 배열로도 문제를 풀 수 있다. dp[j-w] 가 중복되지 않게 뒤에서 부터 K ~ 1 방향으로 아래와 같이 풀 수 있다.

 

import sys

N, K = map(int, sys.stdin.readline().split())
WV = [] 
dp = [0] * (K + 1)  

for i in range(N):
    WV.append(list(map(int, sys.stdin.readline().split())))
    
for i in range(N):
    w, v = WV[i]
    
    for j in range(K, 0, -1):
        if w <= j:
            dp[j] = max(dp[j], dp[j-w] + v)

print(dp[-1])