[Algorithm] Knapsack Algorithm (0/1 배낭 알고리즘)

배낭 문제

배낭 문제란 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고,

일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

짐을 쪼갤 수 있는 경우에는 Fractional Knapsack Problem 으로 부르며, Greedy를 이용해 풀 수 있다.

짐을 쪼갤 수 없는 경우의 배낭문제는 0-1 배낭문제라고 부른다. 이 경우에는 DP를 이용해 문제를 풀 수 있다.

 

https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C

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

 

대표문제

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

풀이

예제 데이터는 다음과 같다.

물건 개수: 4

최대 용량: 7

Index	1	2	3	4
W (Weight)	6	4	3	5
V (Value)	13	8	6	12

 

행은 물건의 index, 열은 배낭의 용량으로 2차 배열을 생성한다.

dp[i][j] = i번째 물건까지 넣을 수 있고, 배낭의 허용 용량이 j일 때 최대 가치

Index/capacity	1	2	3	4	5	6	7
1
2
3
4

 

1. 첫 번째 물건(W: 6, V: 13)의 값을 채워보면, 아래와 같다

Index/capacity	1	2	3	4	5	6	7
1	0	0	0	0	0	13	13
2
3
4

첫 번째 물건은, 물건의 weight가 허용용량보다 같거나 작을 경우에만 물건을 넣는다. 

 

2. 두 번째 물건(W: 4, V: 8)의 값을 채워보자

capacity가 1, 2, 3 일때는 물건의 무게가 허용용량을 초과하였다. 

두 번째 물건을 넣는 것이 아예 불가능 하므로, 이전 인덱스의 최대 가치를 넣어준다. 

이 때의 점화식은 dp[i][j] = dp[i-1][j] 이다.

 

capacity가 4, 5일 때는 두 번째 물건을 넣었기 때문에 최대 가치가 8이다.

capacity가 6일 때는? 두 가지 경우로 생각 할 수 있다. 

 

두 번째 물건을 넣지 않았을 때

이 때의 최대 가치는 dp[1][6](첫 번째 물건까지 넣을 수 있고, 허용 용량이 6일 때의 최대 가치) = 13 이다. 

= dp[i-1][j]

 

두 번째 물건을 넣었을 때

아무 것도 없는 배낭에 두 번째 물건을 넣었다고 가정하면,

배낭의 허용 용량 - 두번 째 물건의 무게 = 남은 허용 용량을 계산할 수 있다.

이미 두 번째 물건을 넣은 상태에서 남은 용량의 최대 가치는 dp[1][남은용량]을 통해 알 수 있다.

여기서는 dp[1][7-4] = dp[1][3] = 0 이고 여기에 두 번째 물건의 가치를 더하면 8이 된다.

= dp[i-1][j-w[i]] + v[i]

 

여기서 점화식을 세울 수 있다. dp[i][j] = max(dp[i-1][j],  dp[i-1][j-w[i]] + v[i])

Index/capacity	1	2	3	4	5	6	7
1	0	0	0	0	0	13	13
2	0	0	0	8	8	13	13
3
4

 

3. 세 번째 물건(W: 3, V: 6)의 값을 채워보자

Index/capacity	1	2	3	4	5	6	7
1	0	0	0	0	0	13	13
2	0	0	0	8	8	13	13
3	0	0	6	8	8	13	14
4

capacity가 3일 때는 물건을 넣는다. 

capacity가 4일 때는 물건을 넣지 않는다. 

....

capacity가 7일 때 dp[2][7]의 값과 6+dp[2][4]값을 비교했을때 후자가 더 크므로 14 값이 들어간다.

 

4. 네 번째 물건(W: 5, V: 12)의 값을 채우자

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

최종적으로 dp[4][7]의 값이 답이 된다.

 

소스코드

package dp;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ12865 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int capacity = Integer.parseInt(st.nextToken());
        int[] v = new int[n+1];
        int[] w = new int[n+1];
        int[][] dp = new int[n+1][capacity+1];

        for(int i = 1; i <= n; i++){
            st = new StringTokenizer(br.readLine());
            w[i] = Integer.parseInt(st.nextToken());
            v[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= capacity; j++){
                if(w[i] > j ){
                    dp[i][j] = dp[i-1][j];
                    continue;
                }

                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
            }
        }

        System.out.println(dp[n][capacity]);

    }
}