Knapsack algorithm
- Fractional Knapsack Problem: 담을 수 있는 물건이 나누어질 수 있을 때
- 0-1 Knapsack Problem: 담을 수 있는 물건이 나누어질 수 없을 때
추후 공부할 예정
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):
# 현재 물건
weight, value = stuff[i]
for j in range(1, K + 1):
# 가방에 담을 수 없는 경우
if j < weight:
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])
풀이
결과
참고
1차원 배열 방식