[BOJ] 12865. 평범한 배낭

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

문제 : 배낭 안에 들어갈 수 있는 최대 가치는?

⊙ DP - 다이나믹 프로그래밍

 

DP의 기본 문제 중 하나라고 할 수 있는 배낭 알고리즘입니다.

배낭 알고리즘은 계속해서 넣어야 하기 때문에 2차원 DP 배열이 필요하지만,

저는 그냥 배열을 2개 만들어서 참조형식으로 swap하는 형식을 택했습니다.

 

DP가 움직이기 위해서는 전 단계의 DP 배열이 필요하기 때문에

DP가 이차원 혹은 2가지 배열이 필요합니다.

 

코드는 많이 짧습니다.

DP의 인덱스는 배낭에 들어간 무게입니다.

최대 무게보다 작으면서 물건 무게보다 작을 때, 예전 DP 값을 넣어주고,

아니면 "예전 DP 값"과 "예전 DP 인덱스 - 물건 무게의 DP 값"을 비교하여

이 중 큰 값을 DP에 설정해 줍니다.

 

그 후, 마지막에 swap을 해주기 때문에 예전 DP 값의 제일 큰 값을 출력하면 끝납니다!

 

코드 :

N, K = map(int, input().split())
pre_dp = [0] * (K + 1)
dp = [0] * (K + 1)
for i in range(N):
    W, V = map(int, input().split())
    for j in range(W):
        if K + 1 > j:
            dp[j] = pre_dp[j]
    for j in range(W, K+1):
        dp[j] = max(pre_dp[j-W] + V, pre_dp[j])
    dp, pre_dp = pre_dp, dp
print(max(pre_dp))