냅색(Knapsack:배낭) 문제

출처 : http://devils9curse.tistory.com/11

냅색 문제라는 것이 있습니다.

주어진 가방이 있을 때 가치가 최대한이 되도록 물건을 담는 것이죠.

그런데 각 물건은 무게가 있어서, 원하는 만큼 전부 가방에 담을 수는 없습니다.

이런 냅색 문제에는 여러가지 종류가 있는데요, 거의 대부분 다이나믹으로 해결할 수 있습니다.

우선 한 물건당 물건의 수량이 1개밖에 없고 물건을 쪼갤 수도 없는 0/1 냅색이 있습니다.

이 경우의 다이나믹 테이블 정의와 점화식은 다음과 같습니다.
(W[i]:i번째 물건의 무게, P[i]:i번째 물건의 가치

D[i][j]:i물건까지를 j크기의 가방에 담았을 때 최대 가치
D[i][j]=MAX(D[i-1][j],D[i-1][j-W[i]]+P[i]) :(j>=W[i])
=D[i-1][j] :(j<W[i])

01Knapsack.cpp

그리고 물건을 쪼갤 수는 없지만 물건의 수량이 여러개인 경우로 변형을 할 수 있는데요,

일단 물건의 개수가 유한개로 주어진 경우에는 두가지 풀이가 있습니다.

하나는 각 물건당 여러개를 담았을 때의 무게와 가치를 전부 데이터에 넣어서 0/1 냅색을 하는 것이죠.

또 다른 방법은, 다이나믹을 약간 다르게 돌리는 것입니다.

D[i][j]:i물건까지를 j크기의 가방에 담았을 때 최대 가치
D[i][j]=MAX(D[i-1][j],D[i-1][j-W[i]*k]+P[i]*k) :(j>=W[i]*k)
=D[i-1][j] :(j<W[i]*k)

별 차이는 없죠?

물건의 개수가 무한개로 주어지는 경우를 보겠습니다.

이번에는 1차원 다이나믹만으로도 해결이 가능합니다.

D[j]:j크기의 가방에 담았을 때 최대 가치
D[j]=MAX(D[j],D[j-W[i]]+P[i]) (j>=W[i])

Knapsack.cpp

마지막 경우로는, 물건을 쪼갤 수 있는 경우가 되겠는데요, 이런 경우에는 그리디로도 해결이 가능합니다.

무게 1당 가치가 높은 순으로 넣을 수 있는 만큼 차례대로 넣으면 되죠.

냅색 문제는 여러 방법으로도 활용이 가능하니, 잘 알아 두시는 것이 좋습니다.