[백준]12865번 평범한 배낭 - DP

 

n, k = map(int, input().split())

weight = [[0] * 2 for i in range(n + 1)] # 1부터 인덱스를 사용하기 위해
dp = [[0] * (k + 1) for i in range(n + 1)] # 가방의 크기 * 갯수
for i in range(1, n + 1):
    weight[i][0], weight[i][1] = map(int, input().split())

for i in range(1, n + 1):
    for j in range(1, k + 1):
        if j - weight[i][0] >= 0: # 가방의 크기 - 물건의 크기 >= 0 -> 즉 가방에 넘치지 않게 담을 수 있는가?
            # 이전의 값(i-1)과 물건을 담기전+물건의 가치 중 큰 것 선택
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i][0]] + weight[i][1])
        else: # 가방에 물건이 넘치는 경우
            dp[i][j] = dp[i - 1][j] # 이전의 최대값을 활용

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

 

코드 설명

외부 반복문과 내부 반복문을 이용한다. 만약 가방에 넘치지 않게 담을 수 있다면 이전에 값 vs 물건을 담기전 + 현재 물건의 가치 중 큰 값을 선택하여 저장한다. 가방이 넘치게 된다면 이전의 최대값을 활용한다.

dp 리스트의 맨 마지막에 저장된 값을 출력한다.

 

Point : 이차원 dp 리스트를 이용하여 가방의 무게 별로 담을 수 있는 가치를 저장하는 것이 포인트이다.

만약 현재 가방의 크기에서 물건의 크기를 뺀 값이 0 이상이라면 (즉, 가방에 넘치지 않게 담을 수 있다면)

이전까지 담겨있던 가치와 / 이전에 담겨있던 물건을 담기전의 가치 + 현재 물건의 가치를 비교해 큰 값을 저장하여야 한다.

물건이 넘치게 되는 경우는 이전의 최대값을 그대로 이용한다.