핵심 인사이트

  1. 배낭 문제(Knapsack Problem)는 NP-완전 문제의 대표적 최적화 문제 — 무게 제한이 있는 배낭에 가치 합계를 최대화하는 물건을 고르는 문제로, 0/1 배낭(물건 전체 또는 선택 안 함)과 분수 배낭(일부 가능)으로 나뉜다.
  2. 0/1 배낭 문제는 DP(동적 프로그래밍)로 의사다항 시간(Pseudo-Polynomial) 해결 — O(nW) 시간·공간 복잡도이며, 이는 엄밀히 다항 시간이 아니지만 실용적으로 많은 경우에 효율적이다.
  3. 분수 배낭(Fractional Knapsack)은 그리디로 최적해 — 단위 무게당 가치(value/weight)가 높은 순으로 탐욕적으로 선택하면 최적해를 보장하며, O(n log n) 시간에 해결된다.

Ⅰ. 배낭 문제 유형

배낭 문제 유형:

0/1 배낭 (0-1 Knapsack):
  각 물건: 전체 선택(1) 또는 미선택(0)
  → NP-완전 (다항 시간 알고리즘 미발견)
  → DP로 의사다항 시간

분수 배낭 (Fractional Knapsack):
  물건을 일부분만 선택 가능 (액체, 곡물 등)
  → 그리디로 최적해 O(n log n)

복수 배낭 (Multiple Knapsack):
  배낭이 여러 개
  → 더 복잡 (NP-하드)

경계 배낭 (Bounded Knapsack):
  물건별 최대 수량 제한
  → DP 확장

문제 정의 (0/1 배낭):
  물건 n개: 각 가치 v_i, 무게 w_i
  배낭 용량: W
  
  목적: Σ v_i × x_i 최대화
  조건: Σ w_i × x_i ≤ W
        x_i ∈ {0, 1}

예시:
  물건: (v=60, w=10), (v=100, w=20), (v=120, w=30)
  배낭 용량: W=50
  
  최적: 물건2 + 물건3 → 가치=220, 무게=50

📢 섹션 요약 비유: 0/1 배낭은 여행 가방 싸기 — 무게 제한(용량)에 가장 소중한 물건(가치)을 선택. 물건은 반만 넣을 수 없어요! 분수 배낭은 주스를 반 병 넣을 수 있는 버전.

Ⅱ. DP 풀이 (0/1 배낭)

동적 프로그래밍 풀이:

점화식:
  dp[i][w] = 물건 1..i 중 무게 w 이하에서 최대 가치
  
  dp[i][w] = max(
    dp[i-1][w],          # 물건 i 미선택
    dp[i-1][w-w_i] + v_i # 물건 i 선택 (w ≥ w_i 일 때)
  )

예시:
  물건: A(v=60,w=10), B(v=100,w=20), C(v=120,w=30)
  W=50
  
  dp 테이블 (일부):
  w:  0  10  20  30  40  50
  초기: 0   0   0   0   0   0
  A:  0  60  60  60  60  60
  B:  0  60 100 160 160 160
  C:  0  60 100 160 180 220
  
  최적값: dp[3][50] = 220

추적 (어떤 물건?):
  dp[3][50]=220: C 선택 (220 > dp[2][50]=160)
  dp[2][20]=100: B 선택
  → 물건 B, C 선택

시간/공간 복잡도:
  O(nW) 시간, O(nW) 공간
  n=100, W=10^9 → 실용 불가
  
  공간 최적화: O(W) (1차원 DP)
  dp[w] = max(dp[w], dp[w-w_i]+v_i)
  (역방향 순회)

의사다항 시간:
  O(nW): W가 n의 다항식이 아님
  (W는 입력 값이지 크기가 아님)
  입력 비트수 기준: O(n × 2^b) (b=W 비트수)
  → 다항 시간이 아님!
  
  하지만 실용적 W에서는 효율적

📢 섹션 요약 비유: 배낭 DP는 표 만들기 — "물건 1~2개, 용량 0~W" 모든 경우를 표에 채우기. 작은 문제 답으로 큰 문제 풀기. 표 크기가 nW이므로 W가 크면 느림!

Ⅲ. 그리디 — 분수 배낭

분수 배낭 그리디 풀이:

핵심 아이디어:
  단위 무게당 가치 = v_i / w_i 로 정렬
  → 높은 것부터 최대한 채우기

예시:
  물건: A(v=60,w=10), B(v=100,w=20), C(v=120,w=30)
  단위 가치: A=6, B=5, C=4
  
  W=50:
  A 전체: 무게 10, 가치 60 (남은 W=40)
  B 전체: 무게 20, 가치 100 (남은 W=20)
  C 20/30: 무게 20, 가치 80 (남은 W=0)
  → 총 가치: 240 (최적!)

증명:
  그리디 선택 = 전역 최적
  (교환 논증: 다른 선택으로 교환해도 가치 감소)

시간 복잡도:
  정렬: O(n log n)
  탐욕 선택: O(n)
  → O(n log n)

0/1 vs 분수:
  0/1: 동일 예시 → 최적: 220 (B+C)
  분수: 동일 예시 → 최적: 240 (A+B+C부분)
  
  분수 ≥ 0/1 항상 성립
  (분수는 더 유연한 선택 가능)

📢 섹션 요약 비유: 분수 배낭 그리디는 뷔페 전략 — 가격 대비 맛(단위 가치)이 높은 음식부터 먹기. 배(용량)가 꽉 차면 남은 음식 조금만 담기!

Ⅳ. 근사 알고리즘과 FPT

0/1 배낭 NP-완전 대응:

FPTAS (Fully Polynomial-Time Approximation Scheme):
  (1-ε) 최적 근사 보장
  
  아이디어: 가치를 스케일링해서 DP
  원래 가치: v_i
  스케일 가치: v'_i = floor(v_i × n/ε/v_max)
  
  복잡도: O(n² / ε)
  ε=0.1 → 90% 근사
  ε=0.01 → 99% 근사
  
  → 최적에 가까운 해를 다항 시간에!

FPT (Fixed-Parameter Tractable):
  파라미터: 물건 수 n 고정
  또는 최적 해의 물건 수 k
  
  O(2^k × poly(n)) — k가 작으면 실용적

분기 한정 (Branch & Bound):
  DP보다 실용적 최적해 탐색
  
  분기: 물건 선택/미선택 분기
  한정: 분수 배낭 상한값으로 가지치기
  → 최적 경로만 탐색

실용적 접근:
  n, W 작음: DP (정확)
  n 작음, W 큼: FPT
  근사해 허용: FPTAS
  실용 최적: 분기 한정법

📢 섹션 요약 비유: 배낭 근사는 충분히 좋은 답 — "완벽한 짐(최적해)" 찾기가 너무 오래 걸리면, "90% 좋은 짐(근사해)"로 타협. FPTAS는 얼마나 타협할지 조절!

Ⅴ. 실무 시나리오 — 클라우드 자원 할당

클라우드 VM 자원 최적 배치 (배낭 변형):

문제:
  가상 서버 100대: 각 CPU 요구량, 비용 효율성
  물리 서버 용량: 128 vCPU
  목표: 비용 효율성 합계 최대화
  
  = 0/1 배낭 문제 형태

접근:
  DP: W=128, n=100
  O(100 × 128) = O(12,800) → 실용적!
  
  빈 패킹 + 배낭의 혼합:
  여러 서버에 VM 분산 배치
  → 복수 배낭 (NP-하드)
  
  실용 접근:
  First Fit Decreasing (FFD) 근사:
  CPU 요구량 높은 VM부터 첫 번째 들어가는 서버에 배치
  → 최적의 약 11/9 × OPT + 6/9 보장

자원 스케줄링:
  Kubernetes 스케줄러 = 배낭 변형
  Pod 요청 (CPU, 메모리) = 무게
  노드 가용 자원 = 배낭 용량
  
  Bin Packing + First Fit 전략
  → 노드 수 최소화 + 자원 효율 최대화

데이터 선택 문제:
  캐시 크기 제한 + 데이터 접근 빈도/크기
  = 배낭 문제 직접 적용
  LRU는 그리디 근사

📢 섹션 요약 비유: 클라우드 배낭 = Kubernetes 스케줄러 — 서버(배낭)에 컨테이너(물건)를 CPU/메모리(무게) 제한 안에서 최대한 효율적으로 배치!

📌 관련 개념 맵

배낭 문제 (Knapsack)
+-- 유형
|   +-- 0/1 배낭 (NP-완전) → DP
|   +-- 분수 배낭 → 그리디 O(n log n)
|   +-- 복수/경계 배낭 → 확장 DP
+-- 풀이
|   +-- DP: O(nW) 의사다항
|   +-- 그리디 (분수 배낭만)
|   +-- FPTAS: (1-ε) 근사
|   +-- 분기 한정
+-- 응용
    +-- 자원 할당, 캐시 최적화
    +-- 빈 패킹 (클라우드)
    +-- 포트폴리오 최적화

📈 관련 키워드 및 발전 흐름도

[배낭 문제 정의 (1957)]
Dantzig: 분수 배낭 그리디 제안
      |
      v
[DP 풀이 (1950~60s)]
0/1 배낭 DP 체계화
의사다항 시간 알고리즘
      |
      v
[NP-완전 확인 (1975)]
Karp: NP-완전 21개 문제 중 포함
      |
      v
[FPTAS 개발 (1977~)]
이브라히모프 등
다항 시간 근사 체계화
      |
      v
[현재 응용]
클라우드 자원 할당
AI 하이퍼파라미터 탐색
금융 포트폴리오 최적화

👶 어린이를 위한 3줄 비유 설명

  1. 배낭 문제는 여행 가방 싸기 — 무게 제한(배낭 용량) 안에서 가장 소중한 물건들을 고르는 것. 어떤 물건 넣을지가 퀴즈!
  2. DP는 모든 경우 표 만들기 — "물건 1개/용량 0~W", "물건 2개/용량 0~W"... 표를 채우면서 최적해를 찾아요.
  3. 분수 배낭은 그리디로 OK — 쪼갤 수 있으면 "가성비 좋은 것부터"가 항상 최적! 쪼갤 수 없으면 DP 필요.