7-11. 그리디: Fractional Knapsack Problem (분수 배낭 문제)

1. 분수 배낭 문제 소개

분수 배낭 문제(Fractional Knapsack Problem)는 탐욕 알고리즘(Greedy Algorithm)을 사용하여 최적의 해를 구할 수 있는 대표적인 문제 중 하나입니다. 이 문제는 0/1 배낭 문제와는 다르게, 물건을 쪼개서 배낭에 넣을 수 있다는 특징을 가지고 있습니다. 즉, 물건의 일부분을 배낭에 넣어 배낭의 용량을 채우면서, 배낭에 담긴 물건들의 가치의 합을 최대화하는 것이 목표입니다.

배경: 이 문제는 자원 할당, 투자 계획 등 다양한 실생활 문제에 적용될 수 있습니다. 예를 들어, 예산 제약 하에 여러 투자 프로젝트 중 일부를 선택하여 투자를 진행할 때, 각 프로젝트의 수익률과 투자 비용을 고려하여 최적의 투자 조합을 찾는 데 활용될 수 있습니다.

2. 문제 정의

분수 배낭 문제는 다음과 같이 정의됩니다.

• 입력:
  • n개의 물건: 각 물건 i는 (가치, 무게) 쌍으로 표현됩니다. 즉, (v_i, w_i)
  • 배낭의 최대 용량 W
• 목표:
  • 배낭에 담을 물건들의 가치의 합을 최대화합니다.
  • 각 물건 i에 대해 0 <= x_i <<mark class="highlight"><strong><u> 1을 만족하도록 합니다. 여기서 x_i는 물건 i를 얼마나 (비율로) 배낭에 넣을지를 나타냅니다. 즉, x_i </u></strong></mark> 1은 물건 전체를, x_i = 0은 물건을 전혀 넣지 않음을 의미합니다.
  • 배낭의 무게 제한을 넘지 않도록 합니다. 즉, $\sum_{i=1}^{n} x_i * w_i <= W$를 만족해야 합니다.
• 수식 표현:
  • 최대화할 가치: Maximize ∑(x_i * v_i)
  • 제약 조건: ∑(x_i * w_i) <= W, 0 <= x_i <= 1

3. 탐욕 알고리즘의 적용: 핵심 원리

분수 배낭 문제는 탐욕 알고리즘을 사용하여 효과적으로 해결할 수 있습니다. 탐욕 알고리즘은 각 단계에서 최선의 선택을 함으로써 전체 문제에 대한 최적해를 찾는 방식입니다. 분수 배낭 문제의 경우, 다음과 같은 단계를 따릅니다.

1. 각 물건의 가치/무게 비율 계산: 각 물건의 가치/무게 비율, 즉 v_i / w_i를 계산합니다. 이 비율은 단위 무게당 가치를 나타내므로, 이 비율이 높은 물건일수록 배낭에 더 많은 가치를 제공합니다.
2. 가치/무게 비율에 따라 정렬: 계산된 가치/무게 비율을 기준으로 내림차순으로 물건들을 정렬합니다.
3. 물건 선택 및 배낭 채우기: 정렬된 순서대로 물건을 선택하여 배낭에 넣습니다.
   • 만약 현재 물건을 통째로 넣을 수 있다면(w_i <<mark class="highlight"><strong><u> 남은 배낭 용량), 물건 전체를 넣습니다(x_i </u></strong></mark> 1).
   • 만약 현재 물건을 통째로 넣을 수 없다면(w_i > 남은 배낭 용량), 남은 배낭 용량에 맞춰 물건의 일부분을 넣습니다(x_i = 남은 배낭 용량 / w_i).
4. 반복: 배낭이 가득 찰 때까지 3단계를 반복합니다.

이러한 탐욕적인 선택은 각 단계에서 가장 높은 가치를 얻을 수 있는 물건을 선택함으로써 전역 최적해를 보장합니다.

4. 예시

다음과 같은 예시를 통해 분수 배낭 문제를 풀어보겠습니다.

• 물건:
  • 물건 1: 가치 60, 무게 10
  • 물건 2: 가치 100, 무게 20
  • 물건 3: 가치 120, 무게 30
• 배낭 용량 W = 50

1. 가치/무게 비율 계산:
   • 물건 1: 60 / 10 = 6
   • 물건 2: 100 / 20 = 5
   • 물건 3: 120 / 30 = 4
2. 가치/무게 비율에 따라 정렬:
   • 물건 1 (6)
   • 물건 2 (5)
   • 물건 3 (4)
3. 물건 선택 및 배낭 채우기:
   • 물건 1: 무게 10, 배낭에 넣을 수 있음. 배낭 용량: 50 - 10 = 40, 총 가치: 60
   • 물건 2: 무게 20, 배낭에 넣을 수 있음. 배낭 용량: 40 - 20 20, 총 가치: 60 + 100 160
   • 물건 3: 무게 30, 배낭 용량 20보다 큼. 물건 3의 일부분을 넣음: 20 / 30 2/3. 총 가치: 160 + (120 * 2/3) 160 + 80 = 240
4. 최종 결과: 물건 1 전체, 물건 2 전체, 물건 3의 2/3를 배낭에 넣었을 때 총 가치 240으로 최대화됩니다.

5. 코드 구현 (Python)

분수 배낭 문제를 해결하는 Python 코드는 다음과 같습니다.

def fractional_knapsack(items, capacity):
    """
    분수 배낭 문제를 해결하는 함수

    Args:
        items: 각 물건의 (가치, 무게) 튜플 리스트
        capacity: 배낭의 최대 용량

    Returns:
        최대 가치
    """
    # 1. 가치/무게 비율 계산 및 정렬
    for i in range(len(items)):
        items[i] = (items[i][0] / items[i][1], items[i][1], items[i][0])  # (가치/무게, 무게, 가치)
    items.sort(key=lambda x: x[0], reverse=True)

    total_value = 0
    remaining_capacity = capacity
    selected_items = []

    # 2. 물건 선택 및 배낭 채우기
    for value_per_weight, weight, value in items:
        if remaining_capacity >= weight:
            # 물건 전체를 넣을 수 있는 경우
            total_value += value
            remaining_capacity -= weight
            selected_items.append((weight,1,value))
        else:
            # 물건의 일부분을 넣는 경우
            fraction = remaining_capacity / weight
            total_value += value * fraction
            remaining_capacity = 0
            selected_items.append((weight,fraction,value))
            break  # 배낭이 꽉 찼으므로 종료

    return total_value, selected_items

# 예시
items = [(60, 10), (100, 20), (120, 30)]  # (가치, 무게)
capacity = 50
max_value, selected = fractional_knapsack(items, capacity)

print(f"최대 가치: {max_value}")
print(f"선택된 물건: {selected}")

위 코드에서 fractional_knapsack 함수는 물건 리스트와 배낭 용량을 입력으로 받아 최대 가치를 반환합니다. 먼저, 각 물건의 가치/무게 비율을 계산하고 이를 기준으로 물건들을 내림차순으로 정렬합니다. 그 후, 정렬된 순서대로 물건을 배낭에 넣으면서, 배낭이 가득 찰 때까지 반복합니다. 물건의 일부분만 넣어야 하는 경우에는, 남은 배낭 용량에 맞춰 비율을 계산하여 가치를 더합니다.

6. 0/1 배낭 문제와의 비교

분수 배낭 문제는 0/1 배낭 문제와 밀접한 관련이 있지만, 몇 가지 중요한 차이점이 있습니다.

• 0/1 배낭 문제: 물건을 통째로 넣거나, 넣지 않는 두 가지 선택만 가능합니다. 물건의 일부분을 넣는 것은 허용되지 않습니다. 이러한 제약 때문에 0/1 배낭 문제는 분수 배낭 문제보다 더 복잡하며, 탐욕 알고리즘으로는 최적해를 보장할 수 없습니다. 대신, 동적 계획법(Dynamic Programming) 또는 분기 한정(Branch and Bound)과 같은 방법을 사용하여 해결해야 합니다.
• 분수 배낭 문제: 물건을 쪼개서 넣는 것이 가능하기 때문에 탐욕 알고리즘으로 최적해를 쉽게 구할 수 있습니다.

0/1 배낭 문제는 NP-Hard 문제에 속하므로, 분수 배낭 문제보다 더 복잡한 알고리즘을 필요로 합니다.

7. 응용 및 활용 사례

분수 배낭 문제는 다음과 같은 다양한 분야에 응용될 수 있습니다.

• 자원 할당: 제한된 자원을 여러 프로젝트에 할당할 때, 각 프로젝트의 수익성과 자원 소모량을 고려하여 최적의 자원 할당 계획을 수립할 수 있습니다.
• 투자 계획: 예산 제약 하에 여러 투자 프로젝트 중 일부를 선택하여 투자를 진행할 때, 각 프로젝트의 수익률과 투자 비용을 고려하여 최적의 투자 조합을 찾는 데 활용될 수 있습니다.
• 광산 채굴: 광산에서 여러 종류의 광석을 채굴할 때, 각 광석의 가치와 채굴 비용을 고려하여 최적의 채굴 계획을 수립할 수 있습니다.
• 광고 예산 배분: 여러 광고 채널에 예산을 배분할 때, 각 채널의 예상 효과와 비용을 고려하여 최적의 광고 예산 배분 계획을 세울 수 있습니다.
• 포트폴리오 최적화: 금융 포트폴리오를 구성할 때, 각 자산의 기대 수익률과 위험을 고려하여 최적의 포트폴리오를 구성할 수 있습니다.

8. 주의사항과 트러블슈팅

분수 배낭 문제를 구현하고 사용할 때 다음과 같은 사항에 유의해야 합니다.

• 정확한 데이터: 문제에 대한 정확한 데이터를 입력해야 합니다. 특히, 물건의 가치와 무게가 정확하게 주어져야 합니다. 데이터의 부정확성은 잘못된 결과를 초래할 수 있습니다.
• 부동 소수점 오차: 물건의 일부분을 계산할 때 부동 소수점 연산이 사용될 수 있습니다. 부동 소수점 연산은 미세한 오차를 발생시킬 수 있으므로, 결과의 정확성을 보장하기 위해 적절한 처리가 필요할 수 있습니다. 예를 들어, 결과값을 반올림하거나 특정 허용 오차 내에서 결과를 비교하는 등의 방법을 사용할 수 있습니다.
• 무게 단위: 무게의 단위가 일관되게 사용되어야 합니다. 서로 다른 단위를 사용하면 잘못된 결과가 나올 수 있습니다.
• 알고리즘의 효율성: 분수 배낭 문제는 탐욕 알고리즘을 사용하므로 시간 복잡도가 O(n log n)으로 효율적입니다 (정렬 단계에서). 하지만 문제의 규모가 매우 큰 경우에는 알고리즘의 효율성을 고려하여 구현해야 합니다.
• 엣지 케이스 처리: 입력 데이터가 유효한지 확인하고, 엣지 케이스(예: 배낭 용량이 0이거나, 물건의 무게가 0인 경우)에 대한 처리를 고려해야 합니다.

이러한 사항들을 고려하여 분수 배낭 문제를 구현하고 사용하면, 문제 해결에 더욱 효과적으로 접근할 수 있습니다.