골드 V

💡문제 분석 요약

dp

💡알고리즘 설계

여러 아이템의 가치와 무게를 더해서 최종 값인 최대 가치를 가져와야 한다.

여러 아이템의 무게의 합으로 계산해야 하며, 각 아이템이 다음 값에 영향을 주기 때문에 dp에 가깝다.

제한사항: 제한 무게 내로 가방에 넣기.

잘 알려진 문제이지만 잘 분석해보자.

우선 dp이므로 dp를 설계한다. 이때, dp에 저장된 값은 값이어야하며, dp의 각 칸의 위치는 dp의 값을 만드는 매개체로 구성한다. 여기서 매개체는 어느 아이템이냐가 주된 것이며, 제한사항이 있기에 무게도 고려해야하므로 넣는다.

따라서 dp의 구성을 dp[아이템][무게]=가치 로 설정한다.

[몇번째 아이템까지 고려했을때][해당하는 무게] = 총 가치 이며

각 물건을 순차적으로 순회하면서, 무게 한도를 검사한 뒤

넣을 수 있으면 weights[i-1] <= w: 담고 max값을 확인해서 넣는다.

이 아이템을 넣을 수 있을 때[i],

넣었을때의 가치(values[i-1] + dp[i-1][w - weights[i-1]], )vs넣지 않았을때의 가치(dp[i-1][w]) 중 큰 값으로 업데이트 한다.

최종 가치(값)는 n개를 넣었을때 제한 무게(ex. k)라고 하면 dp[n][k]이다.

아이템 1번

💡코드

import sys

input= sys.stdin.readline
item = []
n,k = map(int,input().strip().split(' '))
dp = [[0 for x in range(k + 1)] for x in range(n+1)]
weights=[]
values = []
for _ in range(n):
    w,v = map(int,input().strip().split(' '))
    weights.append(w)
    values.append(v)

item.sort(key=lambda x: x[1])
for i in range(n+1):#0번째 물건부터 시작
    for w in range(k + 1):
        if i == 0 or w == 0:
            dp[i][w] = 0
        elif weights[i-1] <= w:
            dp[i][w] = max(values[i-1] + dp[i-1][w - weights[i-1]], dp[i-1][w])
        else:
            dp[i][w] = dp[i-1][w]
            
print(dp[n][k])

💡 기억할 것

  • dp보다는 정렬부터 생각했는데 이전 값이 이후에 영향을 미치니 dp가 맞다고 확신을 가져야한다. 그리고 dp를 어떻게 구성할지 잘 정해야겠다.
  • 예시를 들어 관계를 확인해보기도 하고 어떻게 영향을 주는지도 파악하자. 여기서 중요한 것은 무엇을 뺴느냐, 그리고 빼도 가치가 높아질 수 있다는 점이다. 따라서 max로 확인한다.