평범한 배낭[백준 12865] - python

 

dp를 접하게 되면 꼭 나오는 냅색(knapsack) 문제이다.

예전에 제대로 학습해두지 않았었고 결국 다른 분들의 코드를 참고했다

import sys 

def BOJ12865() :
  n, k = map(int, sys.stdin.readline().split())
  item_list = [[0,0]]
  dp = [[0] * (k+1) for _ in range(n+1)]
  for _ in range(n) :
    w,v = map(int, sys.stdin.readline().split())
    item_list.append([w,v])
  
  for i in range(1, n+1) :
    for j in range(1, k+1) :
      weight, value = item_list[i]
      if item_list[i][0] <= j :
        dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight] + value)
      else :
        dp[i][j] = dp[i-1][j]

  print(dp[n][k])
  
BOJ12865()

 

 

엑셀에서 아래 과정을 한번만 제대로 해보면 문제 풀이 이해가 잘될 것이다. 이건 장담한다.

 

처음엔 0부터 최대 무게까지 순회하면서 문제를 접근했었는데 몇몇 tc에서 통과를 하지 못해서 다른 분들의 코드를 참고했다.

 

핵심은 

 

현재 상품을 담기전에 담겨있던 무게에서의 최대가치와 현재 상품 가치 + 현재 상품 담기전 현재 무게를 뺀 가방의 최대가치를 더하는 것이다. 여기서 dp 개념이 들어온다.

if item_list[i][0] <= j :
        dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight] + value)

코드에선 이 부분인데 이게 엑셀로 직접 해보기 전에는 절대 생각이 나지 않았다.

 

 

 

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

 

출처: https://suri78.tistory.com/2