Knapsack Problem배낭 문제

dp[i][w] = 처음 i개 물건으로 무게 w 이하일 때 최대 가치
dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi)  if w >= wi

def knapsack_01(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)  # 1D 최적화
    for i in range(n):
        for w in range(capacity, weights[i] - 1, -1):  # 역순
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

def knapsack_unbounded(weights, values, capacity):
    """무한 배낭: 각 물건 무제한 사용"""
    dp = [0] * (capacity + 1)
    for w in range(1, capacity + 1):  # 정순
        for i in range(len(weights)):
            if weights[i] <= w:
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

def knapsack_fractional(weights, values, capacity):
    """분할 가능 배낭: 탐욕법"""
    items = sorted(zip(values, weights), key=lambda x: -x[0]/x[1])
    total = 0
    for v, w in items:
        if capacity <= 0: break
        take = min(w, capacity)
        total += v * (take / w)
        capacity -= take
    return total