배낭 알고리즘(Knapsack Algorithm)

1. 개념

무게 W를 감당할 수 있는 배낭이 있을 때 n개 종류의 다른 가치를 가진 물건을 선택해서 넣어 최대의 가치를 구하는 알고리즘이다.

Knapsack 문제는 0-1 Knapsack과 Fraction Knapsack이 있다.

0-1 Knapsack은 물건을 자를 수 없고, Fraction Knapsack은 자를 수 있다.

2. 구현

물건을 하나씩 담아보면서 용량을 초과하면 담지 않고, 용량을 초과하지 않는다면 담아보고 가치가 더 크면 그 용량의 가치를 바꿔준다.

점화식은 다음과 같다.

D[i][j] = max(D[i-1][j-weight[i]]+price[i], D[i-1][j]);

여기서 D[i][j] 는 D[capacity][n], capacity = 배낭의 용량, n = 물건의 개수로 선언한다.

예제에 있는 코드를 보고 따라서 풀어보면 이해가 빠를 것이다.

[배낭 알고리즘 예제 1 : http://gyutts.tistory.com/129]

[배낭 알고리즘 예제 2 : http://gyutts.tistory.com/131]