Skip to Content
공부알고리즘배낭 문제무한 배낭 문제

무한 배낭 문제

무한 배낭 문제란

각 물건을 여러 개 담을 수 있는 배낭 문제다. 동전 거스름돈 문제가 대표적인 예시다.

알고리즘 시각화

동작 예시

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

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

DP 테이블 구성

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

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

012345678910
000000000000
1(2,3)00336699121215
2(3,4)003467910121315
3(5,7)003467910121315

결과: 최대 가치 = 15 (1번 물건 5개 = 2kg × 5 = 10kg, 가치 3 × 5 = 15)

공간 최적화

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

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

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

왜 순방향인가?

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

복잡도

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

주의사항

  • 순방향 순회 필수: 1차원 DP에서는 반드시 순방향으로
  • 0-1 배낭 문제와 구분: 순회 방향이 정반대 (0-1은 역순, 무한은 순방향)
  • 초기화:
    • 최대 가치: dp[0] = 0, 나머지도 0으로 초기화
    • 최소 개수: dp[0] = 0, 나머지는 INF로 초기화
    • 경우의 수(조합): dp[0] = 1, 나머지는 0으로 초기화
  • 인덱스: 물건은 1번부터, 배열은 0번부터 주의
  • 메모리: W > 100,000이면 메모리 초과 주의

구현 팁

  1. 2차원 DP: 경로 복원 필요하면 사용
  2. 1차원 DP: 최댓값만 필요하면 공간 최적화
  3. 순방향 순회: for w = weight[i]; w <= W; w++
Last updated on
분할 가능한 배낭 문제가장 긴 증가하는 부분 수열