Knapsack Problem (가방 문제)

Knapsack Problem (가방 문제)

개념 및 정의

Knapsack Problem은 주어진 물건들의 가치와 무게, 그리고 한정된 무게의 가방을 가지고 가치의 총합을 최대화하는 문제입니다. 이 문제는 0-1 Knapsack과 Fractional Knapsack 두 가지 주요한 변형이 있습니다.

• 0-1 Knapsack: 물건을 통째로 넣거나 안 넣는 경우만 고려합니다.
• Fractional Knapsack: 물건을 일부분만 넣을 수 있습니다.

장점

1. 응용 분야 다양: 자원의 최적 분배 문제로 볼 수 있어서 다양한 분야에서 활용됩니다.
2. 최적해 보장 가능: 0-1 Knapsack 문제의 경우 다이나믹 프로그래밍을 이용하면 최적해를 보장할 수 있습니다.

단점

1. 계산 복잡성: 0-1 Knapsack은 NP-hard 문제로 알려져 있어, 물건의 수가 많을 경우 계산이 복잡해집니다.

구현방법

• 0-1 Knapsack: 다이나믹 프로그래밍(DP)을 주로 사용합니다.
• Fractional Knapsack: 그리디 알고리즘을 사용해도 최적의 해를 구할 수 있습니다.

예시 코드 (Python)

0-1 Knapsack using Dynamic Programming

def knapSack(W, wt, val, n):
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]

    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][W]

val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))

Fractional Knapsack using Greedy

def fractional_knapsack(value, weight, capacity):
    index = list(range(len(value)))
    ratio = [v/w for v, w in zip(value, weight)]
    index.sort(key=lambda i: ratio[i], reverse=True)

    max_value = 0
    fractions = [0]*len(value)
    for i in index:
        if weight[i] <= capacity:
            fractions[i] = 1
            max_value += value[i]
            capacity -= weight[i]
        else:
            fractions[i] = capacity/weight[i]
            max_value += value[i]*capacity/weight[i]
            break

    return max_value, fractions

value = [60, 100, 120]
weight = [10, 20, 30]
capacity = 50
print(fractional_knapsack(value, weight, capacity))

Knapsack 문제는 최적화 문제를 모델링하는 데 자주 사용되므로 이해하고 있으면 많은 문제에 적용할 수 있습니다. 다이나믹 프로그래밍과 그리디 알고리즘이 모두 활용되기 때문에 알고리즘 스터디에도 좋은 대상입니다.