[백준/DP] 12865 평범한 배낭 (Python, 파이썬)

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

knapsack 이라는 알고리즘으로 풀었다.

DP 테이블을 2차원으로 만들어 값을 채워주면 된다.

값을 채워주는 수식은 다음과 같다.

 

 

최대 무게를 초과할 때는 이전가치를 넣고,

최대 무게를 초과하지 않는다면 이전가치와 새로운 가치와 이전 것의 물품을 뺀 가치를 더한 것 중에서 더 큰 값을 넣어주면 된다.

 

그렇게해서 나온 DP 테이블은 다음과 같다. 반복문을 돌면서 채워지는 DP테이블의 값은 가치이다.

 

N: 물건의 갯수

W: 가방의 무게

 

N\W	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4	0	0	0	6	8	12	13	14

import sys
input=sys.stdin.readline

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

W=[]
V=[]
for _ in range(n):
    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-1]>j:
            knap[i][j]=knap[i-1][j]
        else:
            knap[i][j]=max(knap[i-1][j], V[i-1]+knap[i-1][j-W[i-1]])

print(knap[n][k])