[백준] #12865번 Dynamic Programming python

 

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

12865번: 평범한 배낭

 

오늘은 DP 문제를 풀어보고자 한다.

 

배낭 문제(knapsack)을 풀어보려 고한다.

 

배낭에 넣을 수 있는 최대값이 나오고 한도 안에 물건을 넣어 가치의 합이 최대가 되도록 고르는 방법을 찾는 최적화 문제이다.

 

짐을 쪼개지 않고 푸는 문제이므로 DP로 문제를 해결한다.

 

코드는 아래와 같다.

 

import sys

N, K = map(int, sys.stdin.readline().split())
d = [[0]*(K+1) for _ in range(N+1)]

weight_bag = [[0,0]]
for _ in range(N):
    W, V = map(int, sys.stdin.readline().split())
    weight_bag.append([W,V])
    
for i in range(1, N+1):
    for j in range(1, K+1):
        weight = weight_bag[i][0]
        value = weight_bag[i][1]
        if j < weight:
            d[i][j] = d[i-1][j]
        else:
            d[i][j] = max(d[i-1][j], d[i-1][j-weight]+value)

print(d[N][K])