[노트] 0-1 KnapSack Problem

# 배낭 문제

- n개의 물건과 배낭이 있고, 각 물건에 대해 가치와 무게가 알려져 있다.

- 배낭의 최대 용량을 초과하지 않으면서 배낭에 담을 수 있는 최대 가치는?

 

 

 

- 배낭문제는 물건을 쪼갤 수 있는 Fraction Knapsack Problem과 물건을 쪼갤 수 없는 0-1 KnapSack Problem이 있다.

 

- 배낭문제는 대표적인 DP 문제이다.

 

 

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

N, K = map(int, input().split())

weight = [0]
value = [0]
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)


t = [[0]*(K+1) for _ in range(N+1)]

for i in range(1, N+1):
    for w in range(1, K+1):
        if weight[i] > w:
            t[i][w] = t[i-1][w]

        else:
            val_with = value[i] + t[i-1][w-weight[i]]
            val_without = t[i-1][w]

            t[i][w] = max(val_with, val_without)


print(t[N][K])