냅색 알고리즘

냅색 뜻?

- 쓰지 않을 때에는 접어서 주머니에 넣을 수 있는 간단한 배낭


냅색은 무언가를 담을 수 있는 배낭을 의미한다.

배낭은 크기에 따라 담을 수 있는 양이 제한되어 있다.

즉, 냅색 알고리즘으로 문제를 풀어야 할때는 제한된 양이 정해졌을 때, 그 양에 효율적으로 채워 넣어서 최대의 가치를 구할때 필요하다.

예를들어 
6kg을 담을수 있는 가방이 있다.
아래와 같은 물건 리스트가 있다
1) 가치 4 , 무게 3kg
2) 가치 2 , 무게 1kg
3) 가치 5 , 무게 6kg
4) 가치 6 , 무게 5kg
5) 가치 1 , 무게 2kg
6) 가치 3 , 무게 3kg

여기서 넣을 수 있는 최대의 가치는 몇인가?


이 문제는 DP( Dynamic Programming ) 으로 풀어야 한다.
DP 란? 큰 문제를 작은 문제로 나누어서 푸는 방법을 말한다.
위에 예시에서 총 6개의 물건을 6kg에 최대의 가치를 담아야한다.
처음부터 한번에 바로 최대의 가치를 판단하기 어렵다.
그래서 작은 단위 부터 구하면서 올라가야 한다.

배낭 최대 무게가 1kg일때 최대로 넣을 수 있는 물건가치
배낭 최대 무게가 2kg일때 최대로 넣을 수 있는 물건가치
배낭 최대 무게가 3kg일때 최대로 넣을 수 있는 물건가치
....

이런식으로 밑에서부터 올라와야 6kg 이 최대일때 최대로 넣을 수 있는 물건가치를 알 수 있다.
최대무게가 작은것부터 원래 풀려는 최대무게까지 올라가면서 작업을 하니 DP라고 볼 수 있다.

그럼 배낭 제한 무게가 1일때 부터 최대로 넣을 수 있는 물건가치 값을 담을 수 있는 2차원 배열을 만들어보자

dp[v][w] 
여기서 v는 몇번째 물건을 나타낸다. v가 3이면 3번째 물건까지 봤을때를 의미한다.
w는 최대로 담을 수 있는 배낭 무게를 의미한다. w가 5이면 배낭 최대 무게가 5kg일때를 의미한다.
dp[3][5] 는 3번째 물건까지 봤을때 배낭 담을 수 있는 최대 무게가 5kg이면  담을 수 있는 최대 가치를 의미한다.

우리는 최대 6kg에 6개의 물건을 봤을때 최대 가치 즉, dp[6][6]을 구하면 답을 구할 수 있다.

 

dp[v][0] 은 최대 무게가 0kg이니 담을 수 있는 물건이 없어 전부 0이다.

1번 물건의 무게는 3kg으로 w 3이 되어야 담을 수 있다. 그래서 dp[1][0], dp[1][1], dp[1][2] 가 전부 0이다.
dp[1][3] 은 1번 물건이 들어갈 수 있어서 최대 가치는 4가된다. dp[1][w]는 1번째 물건까지 봤으니 
dp[1][4], dp[1][5], dp[1][6] 은 전부 4가 된다.

2번 물건의 무게는 1kg으로 w 1이 되어야 담을 수 있다. 그래서 dp[2][1] 은 2이다. dp[2][2]는 1번 물건이 못들어가니 2번 물건을 담아 2가 된다. 

여기서 중요한 dp[2][3]을 보자 
1번 물건과 2번 물건의 무게를 합치면 4kg이다. 따라서 둘중에 하나만 넣어야 한다. 

2번 물건을 넣었을때랑 넣지 않았을때를 비교해보자.

2번 물건을 넣는경우 => 2번 물건의 가치 2 + 배낭 최대 무게에서 2번 물건의 무게를 뺀 무게에서 그전 물건까지 봤을때 최대 가치 => 2(2번 물건 가치) + dp[2-1][3-2] => 2 + 0 => 2
정리하면 2번 물건을 넣었으니 가치 2가 생겼고, 배낭 최대 무게 3에서 2번 물건의 무게 1을 빼준 무게애서 2번 물건 전인 1번째 물건까지 봤을때 최대 무게를 더해주면 된다.

2번 물건을 넣지 않는 경우 => 2번 물건을 넣기 전인 1번 물건까지 봤을때 무게가 최대 3일때 가치 => dp[2-1][3] => 4 이된다.

2번 물건을 넣으면 가치가 2가 되고, 2번 물건을 넣지 않으면 1번 물건을 넣어 가치가 4가 된다.
둘중 2번 물건을 넣지 않는 경우가 더욱더 큰 가치를 얻을 수 있다.

위에서 도출한 방식을 식으로 정리하면 다음과 같다.

dp[v][w] = max(dp[v-1][w] , (v번째 물건 가치) + dp[v-1][w - (v번째 물건 무게)])
            = max(v번째 물건을 넣지 않은 경우, v번째 물건을 넣은 경우)


dp[2][4]를 보면 1번째 물건과 2번째 물건의 합이 4kg으로 둘다 배낭에 들어갈 수 있다.
위에 도출한 식에 넣으면
dp[2][4] = max(dp[1][4] , 2 + dp[1][3]) = 6 이식을 반복하여 모든 값을 채워 넣어주면
dp[6][6]은 8이 된다.

 

이거를 자바 소스로 정리하면 다음과 같다.

 

package thispack;

import java.util.ArrayList;
import java.util.Scanner;

class Item{
	int value;
	int weight;
	
	Item(int value, int weight){
		this.value = value;
		this.weight = weight;
	}

}

public class Test {

	
	public static void main(String[] args) {
		

		
		Scanner in=new Scanner(System.in);
		
		int n = in.nextInt();//물건 개수
		int limit = in.nextInt();//제한 무게
		int[][] dp = new int[n+1][limit+1];
		
		ArrayList<Item> list = new ArrayList<>();
		
		//물건 가치 및 무게 입력
		for(int i = 0; i < n ; i++) {
			int value = in.nextInt();
			int time = in.nextInt();
			
			list.add(new Item(value, time));
		}
		
		
		//i : 몇번째 물건인지, j : 제한무게
		for(int i = 0; i <= list.size(); i++) {
			
			int v = 0;
			int w = 0;
			
			if(i > 0) {
				v = list.get(i-1).value;
				w = list.get(i-1).weight;
			}
			
			for(int j = 0; j <= limit ; j++) {

				//0번째 물건이거나 제한무게가 0 이면 0입력
				if( i==0 || j==0) {
					dp[i][j] = 0;
					continue;
				}
				
				if(j - w >= 0) {//제한무게 - 물건무게가 0 이상이면 배낭에 담을 수 있는 무게
					//물건을 담는거랑 담지 않는거 중에서 큰 가치를 담아줌
					dp[i][j] = Math.max( dp[i-1][j], v + dp[i-1][j-w]);
				}else {//제한무게를 초과하는 물건
					//i번째 이전인 i-1 번째 물건까지 봤을때 최대 가치를 담아줌
					dp[i][j] = dp[i-1][j];
				}
				
			}
		}
		
	}

}