배낭 문제

배낭 문제(Knapsack Problem)는 조합 최적화의 유명한 문제이다.

한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고,
일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

이 때 짐을 쪼갤 수 있다면 분할가능 배낭문제,
쪼갤 수 없다면 0-1 배낭문제 라고 한다.

0-1 배낭 문제

무게 제한이 50인 배낭에 다음과 같은 세 개의 물건을 넣는 문제이다.
넣은 물건들의 가치(v) 합이 최대가 되면 된다.

 

 

직관적으로 2,3번 물건을 넣어서 무게는 50에 맞추고, 가치를 220으로 하면 최적이다.

 

zeroOneKnapsack(item, cap){
	for i <- 0 to item.length{
		for j <- 0 to capacity{ //배낭 무게까지
        	if i==0 || j==0
				m[i][j] = 0; // 물건이나 무게가 없는 경우
          	else if item[i-1][2] > j
				m[i][j] = m[i-1][j];
            else
				m[i][j] = max(m[i-1][j],m[i-1][j-item[i-1][2]] + item[i-1][1]);
      return m[item.length][cap];

m이라는 배열에 메모이제이션을 한다.

m[i][w]는 i개의 물건과 w의 무게 제한으로 가능한 최대 가치를 의미한다.
m[0][0] 부터 순차적으로 구해나간다.

아무 물건도 선택하지 않았거나 무게가 없는 경우, m[i][w] = 0이다.
i번째 물건의 무게가 무게 제한을 초과하는 경우는 m[i][w] = m[i-1][w]이다.
즉, 마지막에 넣은 물건 하나를 다시 뺀 가치가 답이 된다.

초과하지 않는 경우는 m[i][w] = max(m[i-1][w], m[i-1,w-무게]+가치)이다.
마지막 물건 하나를 뺀 가치와 이전 물건을 뺀 후 새로 넣은 물건의 가치 중 큰 값을 고르면 된다.