백준 12865 평범한 배낭 - Python

출처 : 

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

12865번: 평범한 배낭

import sys

n, k = map(int, input().split())
bag = [[0,0]]
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]

for _ in range(n):
    bag.append(list(map(int, input().split())))
    
for i in range(1, n+1):
    for j in range(1,k+1):
        w = bag[i][0]
        v = bag[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])

 

풀이 : 

 

2차원 행렬로 만들어서  풀어야 하는 문제다.

냅색문제라고 하는 이 문제는 가방에 넣어보고 무게가 안맞거나 더 좋은게 있으면 뺏다가 다른 것을 넣으면서 계산해야하는 복잡한 문제다.

 

행을 무게. 열을 가방에 최대한 들어가는 양으로 설정해준다.

 

그래서 행을 정한다음 열은 0부터 가방에 최대로 들어가는 양 7 까지 쭉 돌아가면서 확인해준다.

 

만일 가방에 무게가 4키로그램 ( dp[2][j]) 라면 j 가 0,1,2,3 일때는 이 물건을 담을 수 없을 것이다. 그래서 이 물건을 담기 전 값 무게가 6키로(dp[1][j]) 값을 그대로 써줘야할 것이다.

 

j = 4,5,6,7 이라면 dp[i-1][j-w] ( j=7 일때 무게가 4kg이라면 J-w =3 이였던 가방)에서 현재 가방의 가치 +V 를 더해준 값과 이 물건을 넣기전 값인 dp[i-1][j] 값 중 큰 값을 넣어본다ㅏ.

 

이렇게 진행 한 다음 가장 마지막에 있는 dp[n][7]을 출력해준다.

 

-https://claude-u.tistory.com/208