[백준] 12865번 평범한 배낭 파이썬

DP 유형에 속하는 여러 문제들을 풀어보고자 해당 문제를 골랐다.

 

필요하다고 생각하는 N개의 물건에는 각각 무게 W와 가치 V가 있고, 최대 K만큼의 무게까지만 배낭에 담을 수 있다. 최대한 즐거운 여행을 할 수 있도록 물건들의 가치의 최댓값을 찾아야 한다.

 

12865번 평범한 배낭 풀이

[시도1]  맞았습니다!! with 솔루션

N, K = map(int, input().split())

W = [0]
V = [0]
dp = [[0]*(K+1) for _ in range(N+1)]

for _ in range(1, N+1):
  w, v = map(int, input().split())
  W.append(w)
  V.append(v)  

for i in range(1, N+1):
  for j in range(1, K+1):
    if W[i] <= j:
      dp[i][j] = max(V[i] + dp[i-1][j-W[i]], dp[i-1][j])
    else:
      dp[i][j] = dp[i-1][j]

print(dp[i][j])

j의 값이 1부터 K까지 증가되는데 이것은 활용 가능한 배낭의 용량이기 때문에 K만 넘지 않는 선에서 어떤 무게든 가능하다. 그러므로 점화식을 세워보면

1. 현재 물건의 가치 + 현재 물건의 무게를 제외하고 남은 배낭 공간에 넣는 물건들의 가치 =>  V[i] + dp[i-1][j-W[i]]

2. 전 물건까지의 가치(현재 물건을 넣지 않은 전까지의 물건들의 가치) => dp[i-1][j]

1과 2중에서 더 가치가 높은 것을 max로 골라서 dp에 담아준다.

단, if문을 사용해서 현재 넣는 물건의 무게가 배낭이 수용 가능한 무게를 넘으면 현재 물건을 넣지 못하고 이전 물건들만을 가지고 가치를 측정해야 한다.

 

 

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

12865번: 평범한 배낭