12865. 평범한 배낭

문제

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

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

준서가 여행에 필요하다고 생각하는 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)가 주어진다.

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

출력

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

풀이

0-1 Knapsack problem : 무게 k만큼 넣을 수 있는 배낭에 쪼갤 수 없는 물건을 넣을 때 가질 수 있는 가치합의 최댓값을 구하는 알고리즘이다.

[데이터]
1. n : 물건의 개수, k : 배낭에 담을 수 있는 최대 무게
2. w[i] : i 번째 물건의 무게
3. v[i] : i 번째 물건의 가치
4. dp[i][j] : 1~i 번째 물건을 이용해서 무게 j를 만들 때의 최대 가중치

Example

• k = 7
  

0-1 Knapsack problem

• knapsack problem에서 만드는 dp 배열의 0번째 행을 0으로 채워준다.
  • 0번째 행 : 아무런 물건도 사용하지 않는 경우
    
• 순서대로 물건을 넣어보자. 1번째 물건은 무게가 6, 가치가 13이다.
  • 가로는 배낭의 담긴 무게를 의미하여 1번 물건이 무게가 6이기 때문에, 무게 6(7번째 열)부터 물건을 넣을 수 있다.
  • 무게 6 전에 가중치는 1번 물건이 포함되지 않는 경우와 동일하므로, dp[i][j] = dp[i-1][j]인 것을 알 수 있다.
  • 배낭에 무게 6의 물건을 담을 때를 생각해보자. 1번 물건 전까지의 물건으로 무게 6을 채운 경우의 가중치 값은 dp[i-1][j]인 것은 전에 보였다. 그럼 1번 물건을 추가했을 때의 가중치는 어떻게 계산할까?
    • 무게 6에서 1번 물건의 무게(6)를 뺀 경우(dp[i-1][0]))의 가중치에서 1번 물건 하나의 가중치를 더해주면 되는 것을 알 수 있다.
    • 지금까지 구한 무게 1의 최대 가중치 + 1번 물건 = 물건 1을 포함한 무게 6에서의 가중치 이다.
  • 즉, dp[i][j]에서의 최대 가중치는 1번 물건을 넣지 않는 경우(dp[i-1][j])와 1번 물건을 하나 추가하는 경우(dp[i-1]j-w[i]]) 중 큰 값이다.
  • dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]
    
• 2번째 물건은 무게가 4, 가치가 8이다.
  • 1번 물건과 마찬가지로 무게가 4인 물건은 배낭 무게 4부터 넣을 수 있으므로, 이전 가중치는 2번 물건을 넣지 않은 경우(dp[i-1][j])와 동일하다.
  • 배낭 무게 4에서의 가중치는 2번 물건을 넣지 않은 경우의 가중치(dp[i-1][4])와 2번 물건을 하나 추가한 경우의 가중치(dp[i-1][[0] + w[i]) 중 큰 값이다. -> dp[2][4] = max(dp[2][0], dp[1][4]) 8
  • 이 순서대로, 2번 물건에서의 가중치 최대값을 계산하면 아래와 같다.
    

    이미지에서 dp의 각 요소들은 가중치(해당 가중치를 만드는데 쓰인, 물건의 인덱스 값)이다.

• 나머지 물건들에서의 값도 구해보자.
  

정리하자면, 점화식은 dp[i][j] = max(dp[i-1][j], dp[i-1]j-w[i]])이며 구하고자 하는 최대 가중치 값은 dp[n][k]이다.

코드

n, k = map(int, input().split())
w, v = [0],[0]

for _ in range(n) :
  wi, vi = map(int, input().split())
  w.append(wi)
  v.append(vi)

dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
for i in range(1,n+1) :
  for j in range(1,k+1) :
    if j >= w[i] :
      dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])
    else :
      dp[i][j] = dp[i-1][j]

print(dp[n][k])