Knapsack 알고리즘

냅색 알고리즘은 유명한 DP 알고리즘 중 하나이다.
유형은 두가지로 나눌 수 있다.

Fraction Knapsack

물건의 가격을 무게로 나누어 무게 대비 가격이 비싼 순서로 물건을 정렬해서 넣으면 쉽게 해결할 수 있다. 남은 배낭이 감당할 수 있는 무게보다 물건의 무게가 많이 나가면 잘라서 넣으면 된다.
-> Greedy로 해결 가능

0-1 Knapsack

물건을 자를 수 없기 때문에 물건, 물건의 무게, 물건의 가격, 배낭의 남은 용량을 모두 고려해야 한다.
-> DP로 해결 가능

가방에 최대 Mkg까지 담을 수 있을 때, dp[i][j] = 가방에 담은 물건의 무게 합이 i일 때, 처음 j개의 물건 중 담을 수 있는 최대 가치 (1<i<=M)

1. i가 현재 물건의 무게 w보다 작을 때
   현재 물건을 담을 수 없으므로 이전 값 복사

dp[i][j] = dp[i][j-1]

2. i가 현재 물건의 무게 w와 같거나 클 때
   현재 물건을 담을 수 있다.
   물건을 담았을 때와 담지 않았을 때의 가치를 비교해준 뒤 더 큰 값을 할당해준다.
   현재 물건의 가치는 v이다.

dp[i][j] = max(dp[i][j-1], dp[i-w][j-1] + v)

최종적으로 물건의 최대 가치는 dp[가방 크기][물건의 개수]로 구할 수 있다.

Bottom-Up 중복 제거 방식 구현

for (int i = 1; i <= N; i++) {
	// K부터 탐색하여 담을 수 있는 무게 한계치가 넘지 않을 때까지 반복 
	for (int j = M; j - w[i] >= 0; j--) {
		dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
	}
}

구현시 메모리차원에서 일차원이 성능도 좋기때문에 dp를 꼭 2차원으로 둘 필요는 없다.

참고

냅색알고리즘 3가지 풀이 방식
냅색알고리즘