배낭 문제(냅색 문제)

문제

유명한 동적계획법 문제중 하나인 냅색(knapsack) 문제를 풀어 보자. 몇 개의 물건이 있고 각 물건에는 무게와 가치라는 2개의 매개변수가 주어진다. 일정한 무게까지 물건을 배낭에 넣을 수 있다고 할 때 가치의 합계가 최대가 되려면 물건을 배낭에 어떻게 넣어야 할까?

풀이

동적계획법을 적용하는 굉장히 유명한 문제로 동적계획법을 이해하는 정석과 같은 문제이다. 핵심은 전체탐색을 하되 이전에 했던 계산을 다시 재활용 하도록 만든다는 점이다. 이를 위해 이차원 배열을 선언하고 배열은 i번째 선택에서 총무게가 j일 때 가지는 최대 가치로 설정한다. 같은 횟수의 선택일 때 같은 무게에서 이미 구한 값 보다 더 낮은 가치라면 굳이 탐색할 필요가 없으니 수행시간이 상당히 줄어들게 된다. 코드은 다음과 같다.

function knapsack(nowWeight, nowPrice, n, start)

{

if (n > weight.length && start > weight.length) return;

if (dp[n][nowWeight] > nowPrice) return;

dp[n][nowWeight] = nowPrice;

if (maxPrice < nowPrice) maxPrice = nowPrice;

for (int i = start; i < weight.length; i++) {

if (weight[i] + nowWeight <= maxWeight) {

knapsack(weight[i] + nowWeight, n+1, i+1);

}

}

}

코드의 간단함을 위해서 초기 값이 들어오는 변수나 정답을 출력하는 변수는 모두 전역변수인 것으로 처리했다.