재귀 (순수 브루트 포스)

우리의 친구 재귀로 멍청한 브루트 포스 방식이다

시간 복잡도는 $O(2^N)$이다

헌친구 버리고 새친구로 갈아끼자

아이디어

걍 다 담아보며 최댓값 구하는 거다

종료 조건은 전부 고려하고 나면 종료다

코드 예시

def knapsack(i, w):
    if i == N:
        return 0
    if weights[i] > w:
        return knapsack(i + 1, w)  # 담을 수 없으면 skip
    else:
        # 담지 않는 경우 vs 담는 경우 중 최대
        return max(knapsack(i + 1, w), knapsack(i + 1, w - weights[i]) + values[i])

# 입력
weights = [6, 4, 3, 5]
values = [13, 8, 6, 12]
N = len(weights)
W = 7

print("최대 가치:", knapsack(0, W))

단점

당연하게도 중복계산이 많아서 느리다는 거다

재귀 + 메모이제이션 (Top-Down DP)

재귀는 그대로지만 계산한 값은 저장해서 재사용한다

아이디어

dp[i][w]: i번째 이후 물건에서 무게 w로 얻을 수 있는 최대 가치

코드 예시

weights = [6, 4, 3, 5]
values = [13, 8, 6, 12]
N = len(weights)
W = 7

# -1은 아직 계산하지 않았다는 의미
dp = [[-1] * (W + 1) for _ in range(N + 1)]

def knapsack(i, w):
    if i == N:
        return 0
    if dp[i][w] != -1:
        return dp[i][w]
    if weights[i] > w:
        dp[i][w] = knapsack(i + 1, w)
    else:
        dp[i][w] = max(knapsack(i + 1, w), knapsack(i + 1, w - weights[i]) + values[i])
    return dp[i][w]

print("최대 가치:", knapsack(0, W))

장점

탑다운 구조로 구현 쉬움
중복 계산 제거 → $O(N × W)$

DP 테이블 방식 (Bottom-Up)

보통 이걸 자주 쓴다

아이디어

dp[i][w]: i번째 물건까지 고려했을 때, 무게 w에서 최대 가치

코드

weights = [6, 4, 3, 5]
values = [13, 8, 6, 12]
N = len(weights)
W = 7

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for w in range(W + 1):
        if weights[i-1] > w:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])

print("최대 가치:", dp[N][W])

장점

구조적으로 깔끔하고 이해 쉬움
추적(backtracking)도 편리

백트레킹 (DFS 최적화 버전)

불필요한 탐색 미리 자르기 (pruning 가지치기)

아이디어

현재 가치 + 남은 최대 가능한 가치가 정답보다 작다면 더 이상 탐색 X

코드 예시

weights = [6, 4, 3, 5]
values = [13, 8, 6, 12]
N = len(weights)
W = 7

max_value = 0

def backtrack(i, w, value):
    global max_value
    if w > W:
        return
    if i == N:
        max_value = max(max_value, value)
        return
    # 가지치기 조건: 생략 가능
    backtrack(i + 1, w, value)  # 안 담고 진행
    backtrack(i + 1, w + weights[i], value + values[i])  # 담고 진행

backtrack(0, 0, 0)
print("최대 가치:", max_value)

주의

최적화 안하면 재귀보다 느릴 수도?
이거 쓸바에 DP씀 ㅇㅇ

요약

방식	설명	시간 복잡도	특징
순수 재귀	모든 경우 탐색	$O(2^N)$	비효율적, 학습용
재귀 + 메모이제이션	중복 계산 제거	$O(N×W)$	직관적, 깔끔
바텀업 DP	반복문으로 채움	$O(N×W)$	가장 많이 쓰임
백트래킹	DFS + 가지치기	최선 $O(N)$, 최악 $O(2^N)$	문제에 따라 빠름