Knapsack 알고리즘으로 제한된 자원에서 최적 선택하기

용량 제약이 있는 선택 문제를 다루는 방식

Knapsack Algorithm은 비용이나 자원이 한정된 상태에서 선택 가능한 항목의 총가치를 최대화하는 문제를 다룬다. 생산, 물류, 재무, 클라우드 운영에서는 모두 용량 대비 이익을 높여야 하는 순간이 생기며, 배낭 문제는 이를 모델링하는 표준적인 방법이다.

각 품목 (i)의 가치 (v_i), 무게 (w_i), 전체 용량 (W)가 주어졌을 때 선택 변수 (x_i)는 0 또는 1, 혹은 정수로 표현한다. 목표는 (\Sigma v_i x_i)를 최대화하면서 (\Sigma w_i x_i \leq W)를 만족하는 것이다.

문제의 형태에 따라 해법도 달라진다.

0/1 Knapsack은 각 품목을 0개 또는 1개만 선택한다. 결정형은 NP-완전이며, 최적화형은 pseudo-polynomial DP로 풀 수 있다.
Unbounded Knapsack과 Bounded Knapsack은 각각 품목의 무한 선택과 유한 선택을 허용한다.
Fractional Knapsack은 품목을 나눌 수 있다. 가치/무게 비율로 정렬하는 Greedy 방식이 최적해를 제공한다.

0/1 Knapsack의 가중치 기반 DP는 시간복잡도 (O(nW)), 공간복잡도 (O(nW)) 또는 (O(W))다. 용량 (W)가 커지면 부담이 커지므로 값 기반 DP (O(nV))를 대안으로 둘 수 있다. FPTAS는 ((1-\varepsilon))-근사도 제공한다.

상태 전이와 알고리즘 선택

0/1 Knapsack에서 목적함수는 maximize Σ v_i x_i이고, 제약은 Σ w_i x_i ≤ W다. DP 상태는 dp[i][c]로 두며, 이는 (i)번째 품목까지 고려했을 때 용량 (c)에서 얻을 수 있는 최대 가치다.

전이는 다음처럼 구성된다.

dp[i][c] = max(dp[i-1][c], dp[i-1][c-w_i] + v_i)

공간을 줄이려면 1차원 dp[c]를 역순으로 갱신한다. 이 방식으로 공간복잡도는 (O(W))가 된다.

가중치 기반 DP는 (W)가 수만~수십만 수준일 때 권장할 수 있다. 가치 합 (V)가 낮다면 가치 기반 DP가 더 적합하다. Fractional Knapsack에서는 Greedy가 최적이지만, 0/1 문제에서 Greedy는 휴리스틱일 뿐 최적해를 보장하지 않는다.

품목 수 (n)이 수십~백 단위인 대규모 0/1 문제에는 Branch-and-Bound나 Meet-in-the-Middle을 사용할 수 있다. Greedy 분수 해를 상계로 삼고 가지치기를 적용해 탐색 범위를 줄인다.

입력을 줄이고 해를 검증하는 과정

전처리는 계산량뿐 아니라 운영 시 해석 방식에도 영향을 준다. 가치/무게 비율로 정렬한 뒤, 더 무겁고 가치가 낮은 명백한 지배 항목은 제거할 수 있다.

값이나 무게를 (\varepsilon)-근사 기준으로 스케일링하면 DP 상태 공간을 줄일 수 있다. 동일 속성의 품목은 묶어서 처리할 수 있고, Bounded Knapsack을 Unbounded Knapsack 형태로 다룰 때는 이진 분할 기법을 적용한다.

해의 품질은 Greedy 분수 해를 상계로 사용해 판단할 수 있다. 선택 집합을 되살려야 한다면 parent 포인터나 선택 비트를 기록한다. 랜덤 생성 데이터와 작은 케이스의 완전탐색 결과를 대조하는 회귀 테스트도 정확성 검증에 활용한다.

⤢✕

물류, 예산, 클라우드 자원 배분에 적용할 때

물류·창고 피킹에서는 SKU의 무게와 가치(마진 또는 우선순위), 차량이나 박스의 용량을 입력으로 사용한다. 지배 품목을 제거한 뒤 0/1 DP 또는 BnB를 선택하고, 복원한 선택 집합으로 적재 리스트, 총 가치·적재율, 미적재 사유를 만든다.

마케팅 예산 배분에서는 캠페인별 비용을 무게로, 기대 수익을 가치로 두고 총예산을 용량으로 모델링한다. 캠페인 선택 상한이 있다면 Bounded Knapsack으로 표현하며, 값 기반 DP를 적용할 수 있다. 결과는 캠페인 선정 리스트, 예산 사용률, ROI 지표로 제공한다.

포트폴리오를 간소화하는 문제에서는 종목별 최소 매수 단위를 무게로, 기대 수익을 가치로 둔다. 분산과 리스크 제약을 단순화한 뒤 0/1 Knapsack 근사를 적용하고, FPTAS로 (\varepsilon)-근사 보장을 얻는다. 종목 선택, 기대수익 합, 한도 대비 사용량이 결과가 된다.

클라우드 컨테이너 자원 할당에서는 워크로드별 CPU·메모리 요구량과 우선순위 또는 수익을 입력으로 받는다. 메모리처럼 단일 자원 축으로 약화해 0/1 Knapsack을 적용할 수 있으며, 다중 제약은 다차원 Knapsack으로 확장한다. 배치 계획, 미배치 워크로드, 자원 사용률을 함께 확인한다.

비용·자원 사용 측면에서는 적재율 또는 예산 사용률이 5~~20%p 향상되는 경험적 범위를 기대할 수 있다. 기존 규칙 기반 방식과 비교해 3~~15% 가치 증가 사례도 빈발한다. 선택 근거가 일관되게 남으므로 의사결정의 재현성이 높아지고, 시뮬레이션과 시나리오 분석, 운영 정책 표준화도 쉬워진다.

변형별로 달라지는 운용 특성

변형	성능(시간복잡도)	확장성(상태공간)	일관성(최적보장)	안정성(결정성/변동)	운영 편의(구현 난이도)
0/1 DP(가중치)	O(nW)	W에 선형 의존	최적 보장	결정적, 입력 스케일 민감	중간
0/1 DP(가치)	O(nV)	V에 선형 의존	최적 보장	결정적, 값 스케일 민감	중간
Greedy(분수)	O(n log n)	n에 로그-선형	분수형만 최적	결정적, 안정적	낮음
Branch-and-Bound	평균 우수/최악 지수	상계 품질에 의존	최적 보장	가지치기 민감	높음
FPTAS	O(n^3/ε) 등 변형	ε 조절 가능	(1-ε)-근사	결정적, ε에 안정	중간

가중치 기반 0/1 DP 구현

전제조건은 Python 3.10+이며 외부 라이브러리는 필요하지 않다. 무게와 용량은 비음수 정수, 값은 비음수 정수를 가정한다.

# 0/1 Knapsack - 가중치 기반 1차원 DP
# 시간복잡도 O(nW), 공간복잡도 O(W)

from typing import List, Tuple

def knapsack_01(weights: List[int], values: List[int], capacity: int) -> Tuple[int, List[int]]:
    assert len(weights) == len(values), "길이 불일치"
    n = len(weights)
    if capacity < 0 or any(w < 0 for w in weights) or any(v < 0 for v in values):
        raise ValueError("음수 입력 불가")
    dp = [0] * (capacity + 1)
    # 선택 복원을 위한 추적 테이블
    choose = [[False] * (capacity + 1) for _ in range(n)]

    for i in range(n):
        w, v = weights[i], values[i]
        # 역순 순회 필수
        for c in range(capacity, w - 1, -1):
            if dp[c - w] + v > dp[c]:
                dp[c] = dp[c - w] + v
                choose[i][c] = True

    # 복원
    res_value = dp[capacity]
    picked = []
    c = capacity
    for i in range(n - 1, -1, -1):
        if choose[i][c]:
            picked.append(i)
            c -= weights[i]
    picked.reverse()
    return res_value, picked

if __name__ == "__main__":
    weights = [3, 2, 5, 7]
    values  = [4, 3, 8, 10]
    capacity = 10
    best, items = knapsack_01(weights, values, capacity)
    print(best, items)  # 예: 15 [1, 3]

값 기반 DP가 유리한 경우에는 v를 스케일링해 (V) 축을 축소할 수 있다. 선택 집합을 복원할 필요가 없다면 choose를 제거해 공간복잡도 (O(W))를 유지한다. (n)이 큰 경우에는 절반 분할 후 합치는 Meet-in-the-Middle이나 상계 기반 BnB로 확장한다.

최적성, 응답 시간, 운영 가시성의 균형

2차원 DP를 1차원 롤링으로 바꾸면 공간은 줄지만, 복원 데이터를 더하면 메모리 증가는 감수해야 한다. 최적성보다 실시간성이 중요하다면 FPTAS나 Greedy로 근사를 허용하고, (\varepsilon)을 조정해 품질과 시간의 균형을 맞춘다.

지배 제거와 스케일링은 성능을 높이지만 해석 가능성을 낮출 위험이 있다. 어떤 전처리가 적용됐는지 로그와 메타데이터로 남겨야 선택 결과를 운영 정책으로 연결할 수 있다.