배낭 문제(Knapsack Problem)

제한된 용량을 가진 상태에서

 

여러 개의 아이템을 선택하여 최대 가치를 구하는 방식입니다.

 

이때 아이템의 무게를 나눌 수 있는지 없는지로 나눠집니다.

 

1. 0-1 배낭 문제

 

각 아이템은 선택하거나(1) 선택하지 않거나(0) 두 가지 경우만 존재할 경우

DP를 사용하여 해결하며, 시간 복잡도는 O(nW)

문제 정의

• 배낭의 최대 용량이 W
• n개의 아이템이 있으며, 각 아이템 i는 무게 w[i]와 가치 v[i]를 가진다.
• 배낭에 넣을 수 있는 최대 가치를 구하는 것이 목표이다.

 

코드

# 0-1 Knapsack Problem (Dynamic Programming)
def knapsack_01(W, weights, values, n):
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, W + 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][W]

# 테스트
values = [60, 100, 120]
weights = [10, 20, 30]
W = 50
n = len(values)
print(knapsack_01(W, weights, values, n))  # 출력: 220

 

 

2. 분할 가능 배낭 문제

 

각 아이템을 부분적으로 쪼개서 넣을 수 있는 경우

탐욕적 알고리즘으로 해결하며, 시간 복잡도는 O(n log n)

문제 정의

• 배낭의 최대 용량이 W
• n개의 아이템이 있으며, 각 아이템 i는 무게 w[i]와 가치 v[i]를 가진다.
• 배낭에 넣을 수 있는 최대 가치를 구하는 것이 목표이다.

코드

# Fractional Knapsack Problem (Greedy Algorithm)
def fractional_knapsack(W, weights, values):
    items = sorted(zip(weights, values), key=lambda x: x[1]/x[0], reverse=True)
    total_value = 0
    
    for weight, value in items:
        if W >= weight:
            W -= weight
            total_value += value
        else:
            total_value += (W / weight) * value
            break
    
    return total_value

# 테스트
values = [60, 100, 120]
weights = [10, 20, 30]
W = 50
print(fractional_knapsack(W, weights, values))  # 출력: 240.0