배낭채우기 문제(Knapsack)

'욕심쟁이 기법'에 해당되는 글 1건

2007/05/14 배낭채우기 문제(Knapsack) (7)

배낭채우기 문제(Knapsack)

Computer/Algorithms 2007/05/14 19:19

배낭채우기 문제란, 정해진 용량의 배낭이 있을 때, 이 배낭에 주어진 물건을 넣어서 최대한의 가치를 내는 문제이다. 각 물건은 고유한 무게와 가치가 있으며, 배낭에 들어가는 모든 물건의 무게의 합은 배낭 용량을 초과하지 못한다.

이 문제는 크게 0/1 Knapsack과 Fractional Knapsack으로 나뉜다.
0/1 Knapsack : 물건을 쪼갤 수 없다. 항상 배낭에 들어가지 않거나, 들어가거나 둘 중 하나이다. 동적 계획법으로 풀 수 있다. 이 문제의 경우에는 두 가지 유형이 있는데, 물건의 종류당 개수가 한정되어 있는 것과 무한정인 것 두 가지가 있다.
Fractional Knapsack : 물건을 쪼갤 수 있다. 무게당 가치를 구하여 Greedy를 이용해 풀 수 있다.

일반적으로 Knapsack 문제라고 하면 0/1 Knapsack을 가리키는 경우가 많다.
이 문제를 풀기 위해서는 동적 계획법을 적용해야 한다.

다음은 종류당 물건의 개수가 무한인 문제의 경우의 솔루션이다.

Solution 1제일 먼저, 물건의 종류를 늘려가면서 생각한다. 가장 처음에는 물건이 한 종류만 있다고 가정한다. 이럴 경우, 가방의 무게를 증가시키면서 각 경우의 최적해를 구한다.
다음에는 두 번째 물건이 있다고 생각하고, 이 물건을 배낭에 넣을 때의 경우와 원래 구해 놓은 최적해를 비교하여 더 높은 가치를 내는 것을 선택한다.
위의 과정을 반복하면 된다.

Dy[i] : 가방의 용량이 i일 때의 최적해
공간복잡도 : M(가방의 용량), 시간복잡도 : NM(물건의 개수 * 가방의 용량)

다음은 종류당 물건의 개수가 각 1개로 한정되어 있는 경우의 솔루션이다.

Solution 2제일 먼저, 가방의 용량을 늘려가면서 각 용량당 물건의 개수를 늘려가며 생각한다.

Dy[i][j] : 가방의 용량이 i이고 j번째 물건까지만 있을 때의 최적해(얻을 수 있는 최대가치)
Dy[i][j]=MAX(Dy[1 ~ (i-W[j])][j-1]+W[j], Dy[1 ~ i][j-1])
공간복잡도 : MN(가방의 용량 * 물건의 개수), 시간복잡도 : M²N(가방의 용량² * 물건의 개수)

Modified at 5/15 11:37 개수 한정의 경우 솔루션 추가

2008년 1월 19일 이후 작성된 모든 글에 대해서 퍼가는 것을 금지합니다.
퍼가고자 하시는 분은 링크를 달아 주시기 바랍니다.

Posted by Harry