IT용어위키

배낭 문제(Knapsack Problem)는 주어진 용량을 초과하지 않으면서 최대 가치를 얻을 수 있도록 아이템을 선택하는 최적화 문제이다. 이 문제는 NP-완전 문제로 알려져 있으며, 동적 계획법(Dynamic Programming)과 그리디 알고리즘을 사용하여 해결할 수 있다.

문제 정의

배낭 문제는 다음과 같이 정의할 수 있다.

입력
- n개의 아이템이 있으며, 각 아이템은 무게(weight)와 가치(value)를 가진다.
- 배낭(Knapsack)의 최대 허용 무게는 W이다.
목표
- 선택한 아이템들의 무게 합이 W를 초과하지 않으면서, 총 가치의 합을 최대화하는 아이템 조합을 찾는다.

배낭 문제의 종류

배낭 문제는 선택 방식에 따라 여러 가지 유형으로 나뉜다.

0/1 배낭 문제(0/1 Knapsack Problem)
- 각 아이템을 한 번만 선택할 수 있음.
- 동적 계획법(DP)을 사용하여 해결 가능.
분할 가능 배낭 문제(Fractional Knapsack Problem)
- 아이템을 부분적으로 선택할 수 있음.
- 그리디 알고리즘(Greedy Algorithm)으로 O(n log n)에 해결 가능.
다차원 배낭 문제(Multi-Dimensional Knapsack Problem)
- 아이템마다 여러 개의 제약 조건(예: 무게, 부피 등)이 존재.
- 일반적인 동적 계획법으로 해결하기 어려움.
다중 배낭 문제(Multiple Knapsack Problem)
- 여러 개의 배낭이 주어지며, 각 배낭에 아이템을 넣을 수 있음.
- 다중 제한을 고려해야 하므로 계산이 복잡해짐.

0/1 배낭 문제 해결 방법

0/1 배낭 문제는 동적 계획법(DP)을 사용하여 효율적으로 해결할 수 있다.

동적 계획법(DP) 풀이

동적 계획법을 사용하여 다음과 같은 점화식을 정의한다.

dp[i][w] = 최대 i개의 아이템을 고려하고, 배낭의 용량이 w일 때의 최대 가치.
점화식
- dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
- 아이템을 선택하지 않는 경우(dp[i-1][w])와 선택하는 경우(dp[i-1][w - weight[i]] + value[i]) 중 최대값을 선택.

코드 예제

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][capacity]

# 예제 실행
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(knapsack(weights, values, capacity))

출력 결과 예시:
7

분할 가능 배낭 문제(Fractional Knapsack)

분할 가능 배낭 문제는 그리디 알고리즘(Greedy Algorithm)을 사용하여 해결할 수 있다.

가치 대비 무게 비율(value/weight)이 높은 순서대로 아이템을 배낭에 넣는다.
배낭이 꽉 차기 전까지 아이템을 추가하며, 남은 공간만큼 일부 아이템을 넣을 수 있다.

코드 예제

def fractional_knapsack(weights, values, capacity):
    items = sorted(zip(weights, values), key=lambda x: x[1] / x[0], reverse=True)
    total_value = 0

    for weight, value in items:
        if capacity >= weight:
            capacity -= weight
            total_value += value
        else:
            total_value += value * (capacity / weight)
            break

    return total_value

# 예제 실행
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(fractional_knapsack(weights, values, capacity))

출력 결과 예시:
7.5

시간 복잡도

배낭 문제의 해결 방법에 따른 시간 복잡도는 다음과 같다.

0/1 배낭 문제
- 완전 탐색: O(2ⁿ) (모든 조합을 탐색)
- 동적 계획법(DP) 풀이: O(nW) (n: 아이템 개수, W: 배낭 용량)
분할 가능 배낭 문제
- 그리디 알고리즘: O(n log n) (정렬 후 선택)

응용

배낭 문제는 다양한 분야에서 활용된다.

자원 할당
- 제한된 자원을 최적의 방식으로 분배.
투자 포트폴리오 최적화
- 제한된 예산 내에서 최대 수익을 얻을 수 있도록 투자 선택.
데이터 압축
- 제한된 공간 내에서 정보를 효과적으로 저장.
스케줄링 문제
- 제한된 시간 내에서 최대 이익을 얻을 수 있도록 작업 배치.

같이 보기

참고 문헌

Bellman, Richard. "Dynamic Programming." Princeton University Press, 1957.
Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.