배낭 문제 (Kanpsack Algorithm)

동적 계획법을 풀이하면서, 배낭 문제의 개념을 꼭 숙지하고 있으면 좋을 것 같다는 생각이 들었다.

이와 관련된 문제를 보며, 냅색 알고리즘을 이해해보도록 하자.

문제url : https://www.acmicpc.net/problem/12865

 

문제에서는 n=4, k=7이고 각 물건의 무게와 가치가 주어졌다.

6 13 4 8 3 6 5 12

	1번 물건	2번 물건	3번 물건	4번 물건
W(무게)	6	4	3	5
V(가치)	13	8	6	12

DP를 사용하여 문제를 풀이한다고 할 때, dp[i][j]의 의미는 아래와 같다.

dp[i][j] = 처음부터 i번째까지의 물건을 살펴보고, 배낭의 용량이 j일 때 배낭에 들어간 물건의 가치합의 최댓값

따라서, 우리가 찾고자 하는 값은 dp[n][k]이다.

dp[i][j]는 dp[i-1][j]와 dp[i-1][j-w[i]]+v[i]의 값 중 더 큰 값이 들어가게 된다.

 

이 원리에 대해 자세히 살펴보자.

i번째 물건의 무게는 w[i]이며, 가치는 v[i]이다.

1. 용량이 j인 배낭에 i번째 물건을 넣지 않은 경우, 가치합의 최댓값은 dp[i-1][j] 이다. i번째 물건을 넣지 않았기 때문에, i-1번째 물건을 넣었을때까지의 가치합의 최댓값과 동일하다.

2. 용량이 j인 배낭에 i번째 물건을 넣었을 때의 상황은, dp[i-1][j-w[i]]+v[i]가 된다. i-1번째 물건에서 배낭의 용량이 j-w[i]였을 때의 값에, 새롭게 i번째의 물건(가치)를 넣은 값이 된다.

 

예를 들어, dp[2][5]의 값을 구해보자.

* 용량이 5인 배낭에 i=2번째 물건을 넣지 않았을 때의 최댓값은 dp[1][5]에 저장되어 있다.

* 용량이 5인 배낭에 i=2번째 물건을 넣었을 때의 가치합의 값은 dp[2][5-w[2]]+v[2] = dp[2][1] + v[2]가 되는 것이다.

 

이는 즉, 가치합의 최댓값으로 물건이 들어가 있는 용량이 2인 배낭에, i=2번째 물건(무게 4)를 새롭게 넣는 상황이 된다. 

 

이러한 원리로, 코드를 작성하면 아래와 같은 코드를 작성할 수 있다.

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

public class Main {
    static int n,k;
    static int[] w,v;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        w = new int[n + 1];
        v = new int[n + 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());
        }

        dp();
    }

    public static void dp() {
        int[][] dp = new int[n + 1][k + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                if (w[i] <= j) { // i번째 물건을 넣을 수 있는 경우
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        // dp값 출력(테스트)
//        for(int i=0; i<=n; i++) {
//            for(int j=0; j<=k; j++) {
//                System.out.print(dp[i][j] + " ");
//            }
//            System.out.println();
//        }
//        System.out.println();
        System.out.println(dp[n][k]);
    }
}

 

[references]

https://chanhuiseok.github.io/posts/improve-6/