[Algorithm] # 지옥의 Dynamic Programing (feat. 백준 12865)

아 나는 DP 문제에서 정말 많이 막힌다...😇 ㅂ박치네..^^
작년에 알고리즘 수업 들었는데...ㅎ 작년 배운 내용 + 백준씨의 12865와 함께
DP의 대표적인 문제 배낭 문제를 풀어본다...

문제

자 먼저 문제는 이러하다.

식

n > 0 (물품의 수) 이고 K > 0 (전체 무게) 일 때,
전체 무게가 넘지 않도록 n번째 까지의 항목 중에서 얻어진 최고의 이익(Optimal Profit)을
P[n][k]라고 하면,

이런 식이 된다. ( 내가 그려왔다 )

• P[n-1][k] 는 전 단계의 최적값이다.
• Pn + P[n-1][k-ki] 는 n 번째 무게를 비웠을 때 최적값 + n 번째 물건 가격을 더한 값이다.

풀어보자

자 이를 표로 나타내서 설명하면

일단 N * K 행렬을 준비하고...
1. 맨 첫 행을 보면 [6, 13]인 물건만 가지고 각각의 무게를 채운다고 했을 때 6보다 작은 값들은
채울 수 없기 때문에 0이며 6부터 해당 가치인 13을 넣어줬다.
2. 두 번째 행을 보자. 4보다 작은 값들은 채울 수 없기 때문에 0이며, 4부터 해당 가치를 넣을 수 있다.
하지만 문제! 여기서 부터는 전의 물건들, 즉 [6, 13]과 함께 채운다. 때문에 6부터는 6의 가치가 8보다 크므로 13을 넣어준다.
3. 세 번째 행을 보자. 마찬가지로 3보다 작은 값들은 채울 수 없기 때문에 0이며, 3부터 해당 가치를 넣을 수 있다. 여기서도 전의 물건들, 즉 [6, 13], [4, 8] 과 함께 채운다. 4일 때는 4의 물건 가치가 3의 물건 가치보다 크므로 8을 넣어주었다. 또한 6에서도 6의 물건 가치가 가장 크므로 6을 넣어 줬다. 하지만 7에서는 현재 물건을 포함 시키지 않을 경우 [6, 13]만 들어가 13이 최대이지만, 현재 물건이 포함된다면 4의 최대가치룰 포함한 14가 가장 최대 가치가 된다.

위의 식처럼, 해당 물건 인덱스에서 최대 가치는 현재 인덱스의 물건을 넣었을 때의 최댓값과 넣지 않았을 때(바로 전의 최댓값)을 비교해야 한다.

answer 코드

n, k = map(int,input().split())
bag = [[0,0]] # 계산하기 편하게 0인덱스를 미리 추가해줌
bag.extend([list(map(int,input().split())) for _ in range(n)])

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

for i in range(1,n+1):
    for j in range(1,k+1):
        if bag[i][0] <=j: # 현재 
            # 현재 물건을 안 넣었을 때, 현재 물건 넣었을 때 (전의 행에서 현재 무게 뺀 최댓값 + 현재 물건 가치)
            p[i][j] = max(p[i-1][j],p[i-1][j-bag[i][0]]+bag[i][1]) 
        else:
            p[i][j] = p[i-1][j]
print(p[n][k])

DP를 마스터하는 그날까지...