[알고리즘] 배낭문제

https://velog.io/@dh1010a/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B0%EB%82%AD%EB%AC%B8%EC%A0%9C-Knapsack-Problem

알고리즘 - 배낭문제(Knapsack Problem)

 

 

1. 각 dp 배열은 이차원 배열로 선언 한다. dp[ 용량 ][ 각 물건의 무게 ] = 가치

 

2. 이차원 배열을 돌린다. 무게 0 ~ , 각 물건의 무게 0 ~

 

3.  d[ 용량 ] [ 현재 물건의 무게 ] = Math.max( d[ 용량] [ 현재 물건의 무게 - 1 ], d[용량- 현재 물건의 무게][ 현재 물건의 무게 -1 ] + 현재 물건의 가치 ) (물건 삽입 X vs 물건 삽입 O)

 

4.  d[ 용량 ] [ 현재 물건의 무게 - 1 ]  -> 현재 물건을 집어 넣기 직전, 이전 용량(-1) 에서의 최대 가치를 가져온다. (현재 물건 삽입 X)

 

5. d[용량- 현재 물건의 무게][ 현재 물건의 무게 -1 ] + 현재 물건의 가치 -> 많이 헷갈렸던 부분!

 

내가 가방에 현재 물건을 집어 넣지 않았을때의 최대 가치를 구해야 한다! 이는 나를 뺏을때의 최대 가치와 같다!

이를 단순히 d[ 나를 뺀 용량( 용량- 현재 물건의 무게 ) ][현재 물건의 무게] 으로 접근하면 안되는것이.. 이렇게 되면 현재 물건을 포함 가치를 가져오게 될 수도 있다! (현재 물건을 또 집어 넣을수 있다는 이야기)

 

해서...  d[나를 뺀 용량][현재 물건의 무게 -1] 로 접근해야지 "나를 제외한 최대의 가치" 에 올바르게 접근할 수 있다. 

 

요기다가 나의 가치를 더해주면 완성이겠지??

 

d[ wi ] [ wj ] = Math.max( d[ wi ] [ wj - 1 ], d[ wi - wj ][ wj -1 ] + value[wj] 

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
arr = [[0,0]]
for i in range(n):
    arr.append(list(map(int, input().split())))
dp = [[0]*(k+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, k+1):
        if j < arr[i][0]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-arr[i][0]] + arr[i][1])
                
print(dp[n][k])