[알고리즘] 동적 계획법(Dynamic Programming) - 백준 12865번 평범한 배낭

minidoo·2020년 12월 6일
0

알고리즘

목록 보기
77/85
post-thumbnail
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
stuff = [[0,0]]
knapsack = [[0 for _ in range(K + 1)] for _ in range(N+1)]

for _ in range(N):
    stuff.append(list(map(int, input().split())))

for i in range(1, N+1):
    for j in range(1, K+1):
        weight = stuff[i][0]
        value = stuff[i][1]

        if weight > j:
            knapsack[i][j] = knapsack[i-1][j]
        else:
            knapsack[i][j] = max(value+knapsack[i-1][j-weight], knapsack[i-1][j])

print(knapsack[N][K])

풀이과정

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

0개의 댓글