[BOJ]12865普通リュック

12865普通リュック

に答える

NP-Hard問題の1つである暗色問題(バックパック問題).物を順番に見て、入れるかどうかを決めると、バッグの残容量は当然その物の重さより大きい.
バックパック(itemNum,limit)は、itemNum号以前のものよりも考慮されている場合、現在のバックパックの残容量が限界の場合、将来的にitemNumからN号までのものを入れる際に得られる最大の価値です.各問題は、このアイテムを入れるかどうかを決定できるため、O(NV)の合計時間で解決できます.
w,v値を利用するため,2次元配列を用いる.dp[i-1][j-w]+v:w,v物品を入れる時dp[i-1][j]:物を置かない

コード#コード#

import sys
input = sys.stdin.readline 

n,k = map(int,input().split())
bag = [[0,0]]
for i in range(n):
    bag.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): # 버틸 수 있는 무게
        w = bag[i][0] # 물건 무게 
        v = bag[i][1] # 가치
        if w > j: # 물건을 넣지 않는 경우 ( 물건 무게 > 버틸 수 있는 무게)
            dp[i][j] = dp[i-1][j]
        else : 
            dp[i][j] = max(dp[i-1][j-w]+v,dp[i-1][j])

print(dp[n][k])