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

문제

백준 12865번 - 평범한 배낭

해결 과정

• DP를 이용하여 해결
• DP 초기화
  • n * k 의 2차원 배열 dp[n][k]를 만들어 각각의 물건을 선택할 때 마다 최대 가치를 판별
  • dp[n][k]는 N번째 물건까지 살펴보았을 때, 무게가 K인 배낭의 최대 가치
• 물건을 배낭에 담을 때,
  ① 현재 배낭의 허용 무게(j)보다 넣을 물건의 무게(w)가 더 크다면 넣지 않는다. = 이전 배낭 그대로 가지고 간다.

  if j < w:
        dp[i][j] = dp[i-1][j]

  ② 그렇지 않다면, 다음 중 더 나은 가치를 선택하여 넣는다
  • 현재 넣을 물건의 무게(w)만큼 배낭에서 뺀다. 그리고 현재 물건(v)을 넣는다.
    v + dp[i-1][j-w]
  • 현재 물건을 넣지않고 이전 배낭 그대로 가지고 간다.
    dp[i-1][j]
  • 둘 중 더 큰 값을 넣는다.

풀이

import sys

n,k = map(int,sys.stdin.readline().split())

dp = [[0] * (k+1) for _ in range(n+1)]

stuff = [[0,0]]

# [[0, 0], [6, 13], [4, 8], [3, 6], [5, 12]]
for _ in range(n):
  stuff.append(list(map(int,sys.stdin.readline().split())))

# 물품의 수 n, 버틸 수 있는 무게 k
for i in range(1, n+1):
  for j in range(1, k+1):
    w = stuff[i][0]
    v = stuff[i][1]

    if j < w:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(v + dp[i-1][j-w],dp[i-1][j])

print(dp[n][k])

https://huiyu.tistory.com/m/entry/DP-01-Knapsack%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C
https://hongcoding.tistory.com/m/50