아래 예시는 배낭 문제 알고리즘에 해당되는 대표적인 예시 중 하나이다.
도둑이 보석가게에 배낭을 메고 침입했다.
배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다.
각 보석들의 무게와 가격은 알고 있다.
배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은?
알고리즘 문제를 풀다가 위와 비슷한 상황을 직면한 적이 종종있었는데, 그럴때마다 풀릴 듯이 문제가 풀리지 않았어서 배낭 문제를 푸는 법에 대해서 한번 정리해보려고 한다.
위와 같은 문제를 직면할 때마다 들었던 생각은 가장 비싼 보석을 먼저 담으면서, 가방이 찢어지게되는 상황이 발생하면 가방에 있는 보석을 빼는 방식을 생각했었던 것 같은데, 반례가 존재하는 풀이인 것 같다.
위 문제는 dp를 이용해서 가장 효율적으로 풀이할 수 있다.
배낭 문제에서 사용되는 점화식은 아래와 같다.
P[i,w]는 i개의 보석이 있고, 배낭의 무게 한도가 w 일때의 최대 이익을 의미한다.
위 점화식의 의미는 다음과 같다.
- i번째 보석이 배낭의 무게한도보다 무거우면 넣을 수 없으므로,
P[i-1,w]의 값을 가져온다 - i번째 보석을 추가하는게 나은지 아닌지를 판단하고, 그에 맞는 최대값을 리턴한다.
점화식을 보면 알 수 있듯이, (i,w) 크기의 이중 배열이 선언되어야한다.
