[CS기초] Knapsack Problem(배낭 문제)

Knapsack Problem(배낭 문제)

Knapsack Problem은 제한된 무게를 가진 배낭에 물건들을 넣을 때, 가치를 최대로 하기 위해 어떤 물건들을 선택해야 하는지에 대한 조합을 찾는 최적화 문제입니다.

 

이 문제에서는 각 물건마다 무게(weight)와 가치(value)를 지니고 있는데, 배낭이 버틸 수 있는 최대 무게(W)를 초과하지 않으면서 선택한 물건들의 가치 총합이 최대가 되어야 합니다.

 

 

Knapsack Problem의 유형

0/1 Knapsack Problem

• 각 물건을 한 번씩만 선택할 수 있다.
• 선택하거나 하지 않거나(0또는 1)의 선택지만 존재한다.

Fractional Knapsack Problem

• 한 물건을 일부만 쪼개서 담을 수 있다.
• 그리디 알고리즘으로 해결이 가능하다

Unbounded Knapsack Problem

• 한 물건을 여러 번 선택 가능하다

 

0/1 Knapsack의 핵심 알고리즘

점화식 (DP)

dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

• dp[i][w]: i번째 물건까지 고려했을 때, 총 무게가 w인 경우의 최대 가치
• dp[i-1][w]: i번째 물건을 선택하지 않았을 때
• dp[i-1][w-weight[i]] + value[i]: i번째 물건을 선택했을 때

 

파이썬에서 0/1 Knapsack 알고리즘(2차원 DP) 구현

# 물건의 개수 n, 배낭의 최대 무게 k 입력
n, k = map(int, input().split())

# DP 테이블 초기화: d[i][j]는 i번째 물건까지 고려했을 때, 배낭 무게 j일 때의 최대 가치
d = [[0] * (k + 1) for _ in range(n + 1)]

# i번째 물건부터 하나씩 처리
for i in range(1, n + 1):
    # 현재 물건의 무게 w, 가치 v 입력
    w, v = map(int, input().split())
    # 배낭 무게 j를 0부터 k까지 순회
    for j in range(k + 1):
        if j < w:
            # 현재 물건을 담을 수 없는 경우: 이전 물건까지 고려한 최대 가치 그대로 사용
            d[i][j] = d[i - 1][j]
        else:
            # 현재 물건을 담을 수 있는 경우:
            # 1. 안 담는 경우 d[i-1][j]
            # 2. 담는 경우 d[i-1][j-w] + v
            # 둘 중 더 큰 값을 선택
            d[i][j] = max(d[i - 1][j], d[i - 1][j - w] + v)

# 최대 가치 출력 (n개의 물건까지 고려했을 때 배낭 무게 k에서 가능한 최대 가치)
print(max(d[n]))

 

파이썬에서 0/1 Knapsack 알고리즘(1차원 DP) 구현

# 물건의 개수 n, 배낭의 최대 무게 k 입력
n, k = map(int, input().split())

# DP 테이블 초기화: d[j]는 배낭의 무게가 j일 때의 최대 가치
d = [0] * (k + 1)

# n개의 물건에 대해 반복
for _ in range(n):
    # 현재 물건의 무게 w, 가치 v 입력
    w, v = map(int, input().split())
    # 무게 k부터 w까지 거꾸로 순회 (이전 상태를 덮어쓰지 않기 위해 역순으로 처리)
    for i in range(k, w - 1, -1):
        # 현재 무게 i에서 물건을 담을 수 있다면, 담는 경우와 안 담는 경우 중 최댓값 선택
        d[i] = max(d[i], d[i - w] + v)

# 최종적으로 가능한 최대 가치를 출력
print(max(d))

 

0/1 Knapsack - 2차원 DP vs 1차원 DP 비교

항목	2차원 DP 방식	1차원 DP 방식
DP 테이블 구조	d[i][j]: i번째 물건까지 고려, 무게 j일 때 최대 가치	d[j]: 무게 j일 때 최대 가치
공간 복잡도	O(n * k)	O(k)
시간 복잡도	O(n * k)	O(n * k)
구현 난이도	비교적 직관적 (초보자에게 쉬움)	역순 순회 필요 (조금 더 신경 써야 함)
순회 방식	앞에서부터 순회 (j = 0 → k)	뒤에서부터 순회 (j = k → w)
갱신 방식	d[i][j] = max(d[i-1][j], d[i-1][j-w] + v)	d[j] = max(d[j], d[j-w] + v)
덮어쓰기 위험	없음 (이전 행 참조)	있음 → 역순 순회로 해결
사용 예시	메모리 제한이 크지 않을 때 적합	메모리가 제한된 환경에서 유리