[DP] 0 / 1 Knapsack

 

가격은 가치를 의미

담을 수 있는 무게가 정해져 있는 가방(Knapsack)에 쪼갤 수 없는 짐을 담지 않거나 담았을 때 (0/1)
최적의 가치를 찾는 알고리즘

 

배낭 문제(Knapsack Problem 냅색 프라블럼)는 조합 최적화의 유명한 문제이다.

짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라 부르고, 동적계획법(Dynamic Programming)으로 풀 수 있다. 

참고로, 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem)라 부르고, 그리디 알고리즘으로 풀 수 있다.

배낭 문제 - 위키백과, 우리 모두의 백과사전

 

예시

존재하는 물건 개수와 가방에 담을 수 있는 무게, 그 물건들의 무게와 가치를 입력했을 때 가방에 담을 수 있는 최적의 가치를 출력하는 코드이다.

import java.util.Scanner;

public class DP3_KnapsackTest {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();	// 물건갯수
		int W = sc.nextInt();	// 가방무게
		
        // 물건을 index로 구분하고 무게와 가치 저장
		int[] weights = new int[N+1];	// 무게
		int[] profits = new int[N+1];	// 가치
		
		for (int i = 1; i <= N; i++) {	// 물건 i에 따라 무게와 가치를 담기
			weights[i] = sc.nextInt();
			profits[i] = sc.nextInt();
		}

		// 최적의 가치를 저장할 DP 테이블
		int[][] D = new int[N+1][W+1];	

		for (int i = 1; i <= N; i++) {	
			for (int w = 1; w <=W ; w++) {
				if(weights[i] <= w) {
					D[i][w] = Math.max(D[i-1][w], profits[i] + D[i-1][w-weights[i]]);
				}else {
					D[i][w] = D[i-1][w]; 
				}
			}
		}
		System.out.println(D[N][W]);
	}
}
/* input
4
10
5 10
4 40
6 30
3 50
 */ // 90

 

아래는 위의 코드 해석

최적의 가치를 저장할 DP 테이블 

int[][] D = new int[N+1][W+1];

 

DP 테이블의 행을 i번째 물건, 열을 가방의 잔여무게로 지정

int N = sc.nextInt();	// 물건갯수
int W = sc.nextInt();	// 가방무게

int[] weights = new int[N+1];	// 무게
int[] profits = new int[N+1];	// 가치

for (int i = 1; i <= N; i++) {	// 물건 i에 따라 무게와 가치를 담기
	weights[i] = sc.nextInt();
	profits[i] = sc.nextInt();
}

for (int i = 1; i <= N; i++) {
	for (int w = 1; w <=W ; w++) {
		// DP 테이블 만들기
    	}
}

물건 0은 존재하지 않지만 물건 1번도 점화식에 적용시키기 위해 물건 0도 테이블에 포함시킨다. 물건 0부터,무게 0부터 DP 테이블을 채우지만, 배열 디폴트는 0이므로 물건 0인 행과 무게 0인 열은 놔두고 for문 돌린다

테이블의 값

if(weights[i] <= w) { // 물건 i가 가방잔여무게보다 가볍거나 같을때 가방에 넣을수 있다
	D[i][w] = Math.max(D[i-1][w], profits[i] + D[i-1][w-weights[i]]);
}else { //물건이 가방잔여무게보다 무거워서 넣을 수 없다
	D[i][w] = D[i-1][w];
}

테이블의 값은 물건 i 까지 고려했을 때(행) 가방의 잔여무게(열)에 따른 최적의 가치(가치의 최대값)를 저장하는 역할

그니까 무게 w인 가방에 물건 i를 넣을 수 있는지 판단하고 넣을 수 있을 때, 물건 i를 넣어야 최적의 가치인지.. 물건 i를 넣지 않아야 최적의 가치인지 구하는 것. 그 물건을 넣을 수 있다고 무조건 넣는 건 최적의 가치가 아니니까

물건 i를 가방에 넣을 수 있을 때

D[i][w] = Math.max(D[i-1][w], profits[i] + D[i-1][w-weights[i]]);

D[i][w] : 물건 i까지 고려한 가치를 구하는 방법은 가방잔여무게에 따라 다르게 저장한다.
왜냐하면 다음 테이블에서 채워질 물건들의 최적의 가치는 가방잔여무게에 따라 넣을 수 있는지 없는지 달라지기 때문

D[i-1][w] : 직전에 저장한 해당 무게에서의 가치
profits[i] + D[i-1][w-weights[i]] : 자신(물건 i)의 가치 + 이전 물건의 가치(D[i-1][])중에 가방잔여무게에서 자신무게를 뺀 무게를 가진 가치(D[][w-weights[i])

Math.max(,) : 이중에 최적(최대)의 가치를 고른다.. 즉, 물건 i를 담는것을 고려했을 때 미포함, 포함 중 어떤 가치가 나은지 판별

물건 i를 가방에 넣을 수 없을 때

D[i][w] = D[i-1][w];

물건 i까지 고려한 가치는 직전에 저장한 해당무게의 가치(물건 i-1까지 고려한 가치중 최적의 가치)와와 같다

최적의 가치 출력

System.out.println(D[N][W]);

테이블의 마지막 값이 가방의 무게가 W일 때 물건 N개를 넣을 수 있는 최적의 가치이다

+ 공간복잡도 줄이는 방법

두개의 행만 사용한다.

왜냐하면 이전의 가치가 최적의 가치로 저장되어있기 때문에 이전이전의 가치들은 다시 볼필요없다.. 따라서 temp 역할을 하는 두개의 행만 필요하다

D [0] = D[1];

즉, 현재의 가치(D[1][]) 를 이전의 가치(D[0][])로 저장하고 다음 가치를 알아볼 때 다시 현재의 가치(D[1][]) 값으로 저장하면 된다.

import java.util.Scanner;

// Knapsack DP 테이블의 행을 물건 i개로 전부 저장하는 것이 아닌 덮어쓰기를 반복하여 2개의 행으로만 사용하기
// 이게 되는 이유는 이전의 가치가 이전 이전까지 모두 고려한 최적의 가치이기 때문
// 공간복잡도를 줄일 수 있다
public class DP3_KnapsackTest_2row {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int W = sc.nextInt();
		
		int[] weights = new int[N+1];
		int[] profits = new int[N+1];
		
		for (int i = 1; i <= N; i++) {
			weights[i] = sc.nextInt();
			profits[i] = sc.nextInt();
		}

		int[][] D = new int[2][W+1];	// 물건 i까지의 최적의 가치는 이전의 가치만 알면 되기 때문에 두개의 행만 가지고 재사용(덮어쓰기)을 반복하여 구할 수 있다

		for (int i = 1; i <= N; i++) {
			D[1] = new int[W+1];
			for (int w = 1; w <=W ; w++) {

				if(weights[i] <= w) {
					D[1][w] = Math.max(D[0][w], profits[i] + D[0][w-weights[i]]);	// 현재(1)의 가치는 이전(0)의 가치값으로 구한다

				}else {
					D[1][w] = D[0][w];
				}
				//System.out.print(D[1][w]+" ");
			}
			D[0] = new int[W+1];
			D[0] = D[1];	// 물건 i까지(현재까지.D[1][]까지)고려한 최적의 가치를 다음 물건 가치를 알아보기위해 이전 가치 (D[0][])로 저장하고,, 다시 새로 알아본 가치를 D[1][]에 저장하고 반복

			//System.out.println();
		}
		System.out.println(D[0][W]);
	}
}
/*
4
10
5 10
4 40
6 30
3 50
 */ // 90