0-1 Knapsack Problem 최적화 (DP 메모리)

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

items = [
	list(map(int, input().split()))
	for i in range(N)
]

# DP 메모이제이션
dp = [ [0] * (K+1) for _ in range(N+1)]

for i in range(1,N+1):
	for w in range(1,K+1):
		weight = items[i-1][0]
		value = items[i-1][1]

		if weight > w:
			dp[i][w] = dp[i-1][w]
		else:
			# 기존에 만들어 둔 w-weight 최대값 가져 오고, 비교
			dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight] + value)


print(dp[N][K])

(N+1) * (K+1) 사이즈의 배열을 만들어서 메모이제이션하여 풀었다.

혹시 더 나은 방법은 없을까, ChatGPT에게 물어보니

 

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

items = [
    list(map(int, input().split()))
    for _ in range(N)
]

dp = [0] * (K + 1)  # 1차원 DP 배열

for weight, value in items:
    # 무게를 K부터 weight까지 거꾸로 탐색 (값이 덮어쓰이지 않도록)
    for w in range(K, weight - 1, -1):
        dp[w] = max(dp[w], dp[w - weight] + value)

print(dp[K])

 

1.  메모이제이션 한 값 중 쓰이는 건, 직전의 값 리스트이고,  DP를 뒤에서 부터 갱신하면 업데이트와 조회가 꼬이지 않는다.

2. 현재 아이템의 무게보다 (현재) 가방용량이 작은건 고려 할 필요가 없다 = 안들어간다.