0-1 배낭 문제 (0-1 Knapsack Problem)

adulty22 2024. 9. 17. 06:10

0-1 배낭 문제는 NP-완전 문제 중 하나로, 주어진 아이템 중에서 최대 가치를 얻을 수 있도록 배낭에 담는 방법을 찾는 문제이다. 각각의 아이템은 특정한 무게와 가치가 있으며, 배낭은 최대 무게 제한이 있다. 아이템을 쪼갤 수 없기 때문에, 각 아이템을 넣거나 넣지 않는 선택을 해야 하며(즉, 0 또는 1로 선택), 이를 최적화하는 방식이다.

문제 정의:

N개의 아이템이 있고, 각 아이템은 무게 weights[i]와 가치 values[i]를 가진다.
배낭의 용량 W는 한정되어 있으며, 이보다 무게가 큰 아이템들은 넣을 수 없다.
목표는 배낭에 담을 수 있는 최대 가치를 구하는 것이다.

예시:

아이템이 다음과 같다고 가정해 본다:

아이템 1: 무게 2, 가치 3
아이템 2: 무게 3, 가치 4
아이템 3: 무게 4, 가치 5
아이템 4: 무게 5, 가치 6

배낭의 최대 용량이 5인 경우, 배낭에 담을 수 있는 최대 가치는 7이다. 여기서 아이템 1과 아이템 2를 선택하면 무게는 5가 되고, 가치의 합은 7이 된다.

재귀 방식 (중복 계산 문제)

# 기본 재귀 방식 0-1 배낭 문제
def knapsack_recursive(weights, values, W, n):
    if n == 0 or W == 0:
        return 0
    if weights[n - 1] > W:
        return knapsack_recursive(weights, values, W, n - 1)
    else:
        include = values[n - 1] + knapsack_recursive(weights, values, W - weights[n - 1], n - 1)
        exclude = knapsack_recursive(weights, values, W, n - 1)
        return max(include, exclude)

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
W = 5
n = len(weights)
print(knapsack_recursive(weights, values, W, n))  # Output: 7

위 방식은 작은 하위 문제들을 여러 번 중복 계산하므로 비효율적이다.

0-1 배낭 문제 해결 전략

이 문제를 해결하기 위한 기본 아이디어는 동적 프로그래밍(Dynamic Programming)을 사용하여, 주어진 조건에 맞게 최적화된 값을 계산하는 것이다. 문제를 하위 문제로 분할하여, 작은 문제부터 차근차근 해결해 나가는 방식으로 접근한다.

하위 문제 정의

dp[i][w]를 다음과 같이 정의한다:

dp[i][w]는 i번째 아이템까지 고려했을 때, 배낭의 용량이 w일 때의 최대 가치를 의미한다.

점화식:

아이템 i를 넣지 않는 경우: dp[i][w] = dp[i-1][w]
아이템 i를 넣는 경우: dp[i][w] = dp[i-1][w - weights[i-1]] + values[i-1]

최종적으로, 각 아이템을 넣거나 넣지 않았을 때의 최대 가치를 비교하여 더 큰 값을 dp[i][w]에 저장한다.

베이스 케이스:

dp[0][w] = 0: 아이템이 없을 때는 배낭에 아무것도 담을 수 없으므로 가치는 0이다.
dp[i][0] = 0: 배낭의 용량이 0일 때도 마찬가지로, 가치는 0이다.

동적 프로그래밍을 이용한 0-1 배낭 문제 구현

다음은 0-1 배낭 문제를 동적 프로그래밍으로 해결하는 Python 코드이다.

def knapsack(weights, values, W):
    n = len(weights)  # 아이템의 수
    dp = [[0] * (W + 1) for _ in range(n + 1)]  # DP 테이블 초기화 (n+1 x W+1)

    # DP 테이블을 채워나가는 과정
    for i in range(1, n + 1):  # i번째 아이템까지 고려
        for w in range(1, W + 1):  # 배낭 용량 w까지 고려
            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][W]  # 최종적으로 얻을 수 있는 최대 가치

# 테스트 케이스
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
W = 5
print(knapsack(weights, values, W))  # Output: 7

코드 설명:

DP 테이블 초기화: dp[i][w]는 i번째 아이템까지 고려했을 때, 배낭 용량 w에서 얻을 수 있는 최대 가치를 저장한다. 테이블의 크기는 n+1 x W+1이다. (아이템의 개수 +1, 배낭 용량 +1)
점화식 적용: 각 아이템에 대해 두 가지 선택을 한다.
- 아이템을 넣지 않는 경우: 이전 상태에서의 최대 가치를 그대로 가져온다. (dp[i-1][w])
- 아이템을 넣는 경우: 배낭에서 현재 아이템의 무게만큼 뺀 상태에서의 최대 가치에 현재 아이템의 가치를 더한 값을 비교한다. (dp[i-1][w-weights[i-1]] + values[i-1])
결과 반환: dp[n][W]에 최종 결과가 저장되어 있다. 이는 n개의 아이템을 고려했을 때, 배낭 용량 W에서 얻을 수 있는 최대 가치이다.

0-1 배낭 문제의 시간 복잡도

시간 복잡도: O(n * W)
→ n은 아이템의 개수, W는 배낭의 최대 용량이다. DP 테이블을 채우는 데 두 중첩 루프가 사용되므로, 총 시간 복잡도는 아이템의 개수와 배낭 용량의 곱이다.
공간 복잡도: O(n * W)
→ DP 테이블에 n * W개의 값을 저장하므로 공간 복잡도도 동일하다. 만약 공간 최적화가 필요하다면, 테이블을 1차원 배열로 줄여 공간 복잡도를 O(W)로 최적화할 수 있다.

0-1 배낭 문제의 변형

Fractional Knapsack Problem:
- 물건을 쪼갤 수 있는 경우, 즉 물건의 일부분만을 배낭에 넣을 수 있다면, 그리디 알고리즘을 사용하여 문제를 해결할 수 있다. 물건의 단위 무게당 가치를 계산해, 가장 높은 가치를 가진 물건부터 배낭에 넣는다.
다차원 배낭 문제 (Multidimensional Knapsack Problem):
- 여러 개의 제약 조건(예: 여러 배낭, 다양한 자원 제한)이 있을 때, 각 자원에 대해 추가적인 제약을 고려하여 문제를 풀어야 한다. 이는 더 복잡한 형태의 배낭 문제이다.

0-1 배낭 문제는 물건을 쪼갤 수 없는 조건에서, 주어진 물건들 중에서 배낭에 넣을 수 있는 최대 가치를 찾는 문제이다.
동적 프로그래밍(DP)을 사용해 중복된 계산을 피하고, 작은 하위 문제들을 해결함으로써 전체 문제를 풀 수 있다.
시간 복잡도는 O(n * W)로, 배낭의 최대 용량과 아이템 개수에 비례한다.
이 문제는 최적화 문제에서 중요한 문제로, 다양한 변형 문제에도 적용될 수 있다.

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms

728x90