12865: 평범한 배낭 (Python)

<문제 유형> : DP(Dynamic Programming)

 

<구현해야 하는 것>

-1~n번 물건을 순차적으로 살펴보면서 무게 1~k 까지 넣을 수 있는 최대의 가치를 갱신하면서 테이블을 작성해나간다.

-DP 테이블

  · row: 1~n 물건, col: 1~k 배낭에 넣을 수 있는 무게  

  · (1+n)*(1+k) 사이즈의 2D 테이블 

  · dp[i][j]의 의미: i번째 물건까지 살펴본 결과 가방에 j의 무게만큼 넣을 수 있을 때의 최대의 가치 

  · i번째 물건의 무게를 w, 가치를 v 라고 할 때, 

    dp[i][j] = max(  물건 i를 포함시킬 경우 가방에 j의 무게를 넣을 수 있을때의 가치 ,

                            물건 i가 포함되지 않고 가방에 j의 무게를 넣을 수 있을 때의 가치 )

 

    (이때, 물건 i가 포함될때 가방에 j의 무게를 넣을 수 있을 때는

      ( i-1)번째 까지의 물건을 살펴봤을 때 가방에 (j-w)의 무게를 넣을 수 있을때의 가치 + v  가 가방의 가치가 된다)   

 

 

   ☞ 이를 수식으로 나타내면,,

 

     dp[i][j] = max( dp[ i-1][ j-w] + v,  dp[ i-1][ j]) 

   

    ※주의 사항:  물건의 무게가 가방에 넣을 수 있는 무게보다 작거나 같은 경우에만 위의 식으로 dp 테이블을 업데이트 해준다, 물건의 무게가 가방에 넣을 수 있는 무게보다 큰 경우에는 그 물건은 넣을 수 없으므로 

 

    dp[i][j] = dp[i-1][j]    임을 유의하자 

 

- 모든 물건을 살펴본 후 ,  최종 출력은 dp[ n][ k]가 된다. 

---

import sys 
input = sys.stdin.readline 
n, k = map(int, input().split())
things = [()] #각 물건의 (weight, value)이 담겨있음 
for _ in range(n):
    w, v = map(int, input().split())
    things.append((w, v))

# DP- row: 물건 1~k 까지 살펴본 배낭 무게에 넣을 수 있는 최대의 가치 값 , col: 배낭에 넣는 물건의 무게 
# DP: (n+1)*(1+k) 2D-table 
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]

for i in range(1, n+1):
    w, v = things[i]
    for bw in range(1, k+1):
        if bw >= w:
            dp[i][bw] = max(dp[i-1][bw-w]+v, dp[i-1][bw])
        else: #배낭에 넣을 수 있는 무게보다 물건의 무게가 무거운 경우 !!이거 빼먹음!!
            dp[i][bw] = dp[i-1][bw]

print(dp[n][k])