[백준][Python] 1535 안녕 : 0 - 1 knapsack

기본적인 0, 1배낭문제. 열은 hp, 행은 각 선택지.

이전 hp에서 최댓값을 계승할 것이냐? 아니면 새로운 선택지를 취할것이냐?

 

import sys
input = sys.stdin.readline


N = int(input()) 
L = [0] + list(map(int, input().split()))
P = [0] + list(map(int, input().split()))
dp = [[0] * 101 for _ in range(N+1)] 

for i in range(1, N+1): 
    for j in range(1, 101): 
        if L[i] <= j: 
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-L[i]] + P[i]) 
        else: 
            dp[i][j] = dp[i-1][j] 

print(dp[N][99])