기초 DP알고리즘 문제

배낭 알고리즘(a.k.a Knapsack problem)

배낭 알고리즘은 쪼갤 수 없는 물건이 제한된 가방에 최대한의 가치로 담는 문제이다. Fractional Knapsack 문제는 탐욕 알고리즘으로 풀 수 있었지만, 조건에서 쪼갤 수 있어서 가능했다. 앞서 쪼갤 수 없는 물건을 최대한의 가치를 가지며 담기 위해서는 DP를 통해서 해결하게 된다.

Knapsack problem 점화식

알고리즘 설명에 대략적인 설명은 다음과 같다.

  • 넣을 물건 또는 가방이 있는가?
  • 현재 들고 있는 물건을 넣기 위한 공간이 충분한가?
  • 들고 있는 물건을 넣었을 때와 넣지 않았을 때 어느 것이 더 좋은가?

위 과정을 보면 알 수 있듯 문제를 해결하기 위해서는 모든 경우(각각의 물건을 담았을 경우, 담지 않았을 경우)를 계산하여 항상 제일 나은 선택을 유지하며 계산해야 한다. 이때 사용되는 기법이 메모제이션으로 아래와 같이 사용된다.

Knapsack problem 과정

2차원 배열로 가로축은 가방의 현재 무게, 세로 축은 현재 물건의 번호이며 각각의 요소 안에는 제일 나은 선택으로 만들어진 가방의 가치(value)가 기록되며 배열 아래에 물건에 w(weight), v(value)가 기록되어 있다.

Share