BOJ_12865 [ 평범한 배낭 ] [ 파이썬 ]

문제

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

12865번: 평범한 배낭

문제 해결 방법

다이나믹 프로그래밍으로 문제를 해결해야 된다.

첫번째 물건부터 시작해서 현재 물건을 넣었을 때와 넣지 않았을 때 가치 중 큰 값을 갱신해주면 된다.

물건을 넣었을 때와 넣지 않았을 때를 어떤식으로 코드를 구현해야 될까요?

 

통과한 코드를 분석해보면 다음과 같다.

 

for i in 물건개수 :

  for j in 1부터 K까지 무게:

      if 해당 물건 인덱스 무게가 j 보다 작거나 같다면 현재 물건을 넣을 수 있다. (여기서 넣을지 말지 판단을 하게 된다.)

          dp[i][j] = max ( dp[i-1][j] (현재 물건을 안넣은 경우) , dp[i-1][j - w ] + v (현재 물건을 넣은 경우 현재 물건을 뺀 무게 중 가치가 가장 큰 값 + 현재 아이템 가치)

     else  j 무게 중 제일 큰 값을 대입

          dp[i][j] = dp[i-1][j]

소스 코드 보기

https://github.com/jokerKwu/BOJ_Algorithm/blob/master/python/BOJ_12865.py

jokerKwu/BOJ_Algorithm

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
dp = [ [0]*(K+2) for _ in range(N+1) ]

weight = []
value = []
weight.append(0)
value.append(0)
for i in range(1, N+1):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

for i in range(1, N+1):
    for j in range(1, K+1):
        if j >= weight[i]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][K])