[DP 알고리즘] 평범한 배낭 G5

기출 : BOJ #12865

 

현재 상황을 무게가 N이라고 가정했을 때

현재 무게일때 가치의 최댓값(D[n])은 (직전 최댓값(D[n-ai])에 직전에 선택한 물건의 가치(val[ai])를 더한 것)의 최댓값이다

이를 점화식으로 표현하면 다음과 같다

D[n] = max(D[n-ai]+val[ai])

from copy import deepcopy

# D[n] = 무게가 n일때 가질 수 있는 가치의 최댓값, [최댓값을 만들 때 선택된 것들]
# D[n] = max(D[n-ai]+val[ai])

ans = 0
n, k = map(int,input().split())
weight, val = list(), list()
for i in range(n):
    w, v = map(int,input().split())
    weight.append(w)
    val.append(v)
d = [[-1, []] for _ in range(100001)]

# 초기화
for i in range(n):
    if d[weight[i]][0]<val[i]:
        d[weight[i]][1] = [i]
        d[weight[i]][0] = val[i]
    if weight[i]<=k:
        ans = max(ans, val[i])
                
# 무게가 i일때 가치의 최댓값 계산
for i in range(1, k+1):
    apnd = -1
    apndVal = 0
    # j번째 물건을 선택할 경우
    for j in range(n):
        if i-weight[j]>=1:
            if d[i-weight[j]][0] != -1 and j not in d[i-weight[j]][1]:  
                if d[i][0] < d[i-weight[j]][0] + val[j]:
                    if apndVal<d[i-weight[j]][0] + val[j]:
                        apndVal = d[i-weight[j]][0] + val[j]
                        apnd = j
    # 최댓값이 갱신된 경우
    if apnd!=-1:
        d[i][1] = deepcopy(d[i-weight[apnd]][1])
        d[i][1].append(apnd)
        d[i][0] = apndVal
        ans = max(ans, apndVal)

print(ans)