Knapsack 문제(배낭 문제) : DP 최적화

**Knapsack 문제(배낭 문제)**는 조합 최적화 문제로, 주어진 조건 하에서 최대 또는 최적의 결과를 찾는 문제입니다. 이 문제는 동적 계획법(Dynamic Programming)이나 탐욕법(Greedy Algorithm)을 활용하여 풀 수 있습니다. 배낭 문제는 크게 두 가지로 나눌 수 있습니다.

 

1. 0-1 Knapsack 문제

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

    for i in range(1, n + 1):
        for w in range(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]

# Example usage
weights = [5, 4, 6]
values = [10, 40, 30]
W = 10
print(knapsack(weights, values, W))  # Output: 50

 

2. Unbounded Knapsack 문제

def unbounded_knapsack(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)

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

    return dp[W]

# Example usage
weights = [5, 4]
values = [10, 40]
W = 10
print(unbounded_knapsack(weights, values, W))  # Output: 100