< DP > 12865번 평범한 배낭 with 파이썬

 

문제

 이 문제는 아주 평범한 배낭에 관한 문제이다.

 

 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

 

 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

 한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

정답비율

36.512%

알고리즘 분류

 #DP #다이나믹프로그래밍

 

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
dp = [[0]*(k+1) for _ in range(n+1)]
lst = [(0, 0)]
for _ in range(n):
    w, v = map(int, input().split())
    lst.append((w, v))

for i in range(1, n+1):
    nw, nv = lst[i][0], lst[i][1]
    for j in range(1, k+1):
        if j >= nw :
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-nw] + nv)
        else :
            dp[i][j] = dp[i-1][j]
print(dp[-1][-1])

 

- 꽤 대표적인 dp문제 중 하나이다. 비슷한 문제를 프로그래머스에서 풀었던 기억이 있다.

 

  - 초기 dp그래프를 위와 같이 설정하였다. 각 열은 그 무게에서의 최대 가치값이고, 각 행은 물품의 누적이다. n값을 이용하기 위해서 0을 추가하였고, dp의 점화식을 사용하려면 위 쪽 행을 이용해야하므로 빈값인 (0,0) 을 넣었다.

 

 - 설명을 위해서 필요한 부분에 색을 칠해두었다.

 

 - 먼저 푸른 부분을 보자. dp를 채울 때, 그 때의 무게인 6이상의 경우에만 채워졌음을 알 수 있다. 그 이전은 그 윗 행의 값을 따른다.

 

 - 다음으로 붉은 부분을 보자. 6의무게와 4의 무게가 누적되었을 때의 경우이다. 이 때, 6을 만들 수 있는 경우에서는 4만으로 만드는 8보다 6만으로 만드는 경우가 더 크므로 13이 되었다. 즉 윗 행 값이 만들 수 있는값보다 더 크면 윗 행의 값을 따른다.

 

 - 다음으로 보라색 부분을 보자. 윗행 보다 이 칸에서 만들 수 있는 가치가 더 큰 경우인데, 이를 구하는 식이 중요하다. 현재 누적된 3의 무게를 뺀 4의 무게를 바로 윗행에서 찾아서 더한 것이다. 즉 바로 위에서 누적된것중 4의 무게를 가지는 가치와 현재 새로 추가된 가치를 합하여 이것과 바로 윗행 값을 비교하게된다.

 

 - 위를 종합하여 도출해낸 점화식은 다음과 같다. (nw=새로 추가된 무게, nv=새로 추가된 가치)

 

 dp[i][j] = max(dp[i-1][j], dp[i-1][j-nw] + nv)

 

 - 이 때 조건을 통해 새로 추가된 무게보다 j가 작으면 윗행의 값을 따르도록 한다.

 

 

---

 

참고

 

12865번: 평범한 배낭