[알고리즘] 배낭 문제(Knapsack Problem)

배낭 문제(Knapsack Problem)

배낭 문제란 배낭에 담을 수 있는 무게의 최대값이 정해져 있고,

 

일정한 가치와 무게가 정해져있는 짐들을 배낭에 닮을 때,

 

가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

 

배낭 문제는 크게 

 

1) 물건을 쪼갤 수 있는 배낭문제(Fraction Knapsack Problem)와

 

2) 물건을 쪼갤 수 없는 배낭문제(0/1 Knapsack Problem)으로 나뉜다.

 

1) 물건을 쪼갤 수 있는 배낭문제의 경우는 가치가 큰 물건부터 담고, 남은 무게 만큼 물건을 쪼개는 방식으로

 

그리디 알고리즘으로 해결할 수 있다.

 

2) 물건을 쪼갤 수 없는 배낭문제의 경우는 동적계획법(DP, Dynamic Programming)을 활용해 해결할 수 있다.

 

0/1 Kanpsack Problem 과정

0/1 Knapsack Problem 문제를 해결하기 위해서 동적 계획법을 이용한다.

 

가방에 담을 수 있는 물건의 무게와 가치가 아래 표와 같을 때,

물건	1	2	3	4
무게	6	4	3	5
가치	13	8	6	12

 

2차원 배열을 만들고 각 행과 열에 i번째 물건까지 넣을 수 있고, 배낭에 넣을 수 있는 최대무게가 j일 때, 최대 이윤을 저장해나간다.

 

이 때, 행 i 는 물건 i까지 넣을 수 있을 때를 의미하고, 열 j는 가방의 최대 무게를 의미한다.

 

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2
3
4

 첫 번째 물건(무게 : 6, 가치 : 13)만 넣을 수 있을 때, 가방의 최대 무게에 따른 최대 이윤이다. 

 

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3
4

두 번째 물건(무게 : 4, 가치 : 8)만 넣을 수 있을 때, 가방의 최대 무게에 따른 최대 이윤이다. 

 

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4

세 번째 물건(무게 : 3, 가치 : 6)만 넣을 수 있을 때, 가방의 최대 무게에 따른 최대 이윤이다. 

 

3행 7열을 보면 DP를 사용하는 이유를 알 수 있다. 가방의 최대 무게가 7일 때, 세번째 물건을 넣고 나서도 가방의 무게가 4가 남는다. 

 

그렇다면 가방에는 최대무게가 4일 때와 같은 최대이윤을 더 남길 수 있다.

 

즉, DP[i][j]에는 v[i] + DP[i-1][j-w[i]]가 들어간다.

 

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4	0	0	0	6	8	12	13	14

마지막 사이클까지 돌게되면 최대 이윤이 14인 것을 확인할 수 있다.

 

위의 과정을 점화식으로 나타내면 아래와 같이 나타낼 수 있다.

 

각 가방의 가치 : v[n]

각 가방의 무게 : w[n]

최대이윤 : dp[m][n]이라 할 때,

 

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

 

(w[i] > j) dp[i][j] = dp[i-1][j]

 

0/1 Knapsack Problem 구현

package baekjoon;

import java.util.*;

public class BOJ_12865 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] w = new int[n];
		int[] v = new int[n];
		int[][] dp = new int[n+1][k+1];
		int max = 0;
		for(int i = 0; i < n; i++) {
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
		}
		
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= k; j++) {
				if(w[i-1] <= j)
					dp[i][j] = Math.max(v[i-1] + dp[i-1][j - w[i-1]], dp[i-1][j]);
				else
					dp[i][j] = dp[i-1][j];
				max = Math.max(dp[i][j], max);
			}
		}
		System.out.println(max);
	}
}