Skip to Content
공부알고리즘배낭 문제0-1 배낭 문제

0-1 배낭 문제

0-1 배낭 문제란

가장 기본적인 배낭 문제로, 각 물건을 넣거나 넣지 않는 두 가지 선택만 가능하다. 각 물건을 쪼개거나 여러 개 담을 수 없다.

알고리즘 시각화

동작 예시

아래와 같은 입력이 주어졌을 때 0-1 배낭 알고리즘의 동작 과정을 살펴보자.

  • 배낭 용량: 7kg
  • 물건 목록:
    • 1번: 무게 6kg, 가치 13
    • 2번: 무게 4kg, 가치 8
    • 3번: 무게 3kg, 가치 6
    • 4번: 무게 5kg, 가치 12

DP 테이블 구성

정의: dp[i][w] = i번째 물건까지 고려했을 때 용량 w일 때 얻을 수 있는 최대 가치

점화식: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

01234567
000000000
1(6,13)0000001313
2(4,8)0000881313
3(3,6)0006881314
4(5,12)00068121314

결과: 최대 가치 = 14 (2번 물건 4kg + 3번 물건 3kg = 총 7kg, 가치 8 + 6 = 14)

공간 최적화

2차원 DP는 1차원 배열로 최적화 가능하다. 단, 역순으로 순회해야 같은 물건을 여러 번 선택하는 것을 방지할 수 있다.

1차원 정의: dp[w] = 용량 w일 때 얻을 수 있는 최대 가치

for 각 물건 i:
  for w = W down to weight[i]:  // 역순!
    dp[w] = max(dp[w], dp[w - weight[i]] + value[i])

왜 역순인가?

  • 순방향으로 하면 dp[w - weight[i]]가 이미 같은 물건으로 갱신된 상태
  • 따라서 같은 물건을 여러 번 선택하게 됨 (이것이 0-1 배낭에서 피해야 할 상황)
  • 2차원에서 dp[i-1][w-weight[i]] (이전 행)를 참조하는 것과 동일한 효과

복잡도

구분복잡도설명
시간 복잡도O(N×W)N개 물건 × W 용량
공간 복잡도O(N×W) 또는 O(W)2차원 또는 1차원 최적화

주의사항

  • 역순 순회 필수: 1차원 DP에서는 반드시 역순으로
  • 무한 배낭 문제와 구분: 순회 방향이 정반대 (무한은 순방향, 0-1은 역순)
  • 초기화:
    • 기본: dp[0] = 0, 나머지도 0으로 초기화
    • 정확히 W만 채워야 하는 변형 문제: dp[0] = 0, 나머지는 -INF로 초기화하여 불가능한 상태 표시
  • 인덱스: 물건은 1번부터, 배열은 0번부터 주의
  • 메모리: W > 100,000이면 메모리 초과 주의

구현 팁

  1. 2차원 DP: 경로 복원 필요하면 사용
  2. 1차원 DP: 최댓값만 필요하면 공간 최적화
  3. 역순 순회: for w = W; w >= weight[i]; w--
Last updated on
배낭 문제란?분할 가능한 배낭 문제