[알고리즘] 백준 12865 - 평범한 배낭

문제본문

입력 
[물건의 개수] [최대 무게]
4 7
[물건 무게] [물건 가치]
6 13
4 8
3 6
5 12
________________
출력
[최대 가치]
14

동적프로그래밍의 대표 문제 불리는 Knapsack 알고리즘은 dp를 사용하여 무게와 가치 두 가지 요소로 가질 수 있는 최대 가치를 구하는 문제 유형이다.

 

문제 해설

동적프로그래밍은 dp를 어느 부분으로 잡는 지가 관건 인듯하다. Knapsack은 이중 배열로 dp를 설정한다. dp[i][j]라고 가정하면, i번째까지 물건을 집어 넣는 다고 했을 때, 남아있는 무게가 j라면 얻을 수 있는 최대가치를 뜻한다. 해당 알고리즘은 테이블로 과정을 묘사하면 이해가 더 쉽다.

 

무게	1	2	3	4	5	6	7
1번째 물건	0	0	0	0	0	13	13
2번째 물건	?	?	?	?	?	?	?

 

무게가 6이고 가치가 13인 첫번째 물건부터 가방에 넣는 다는 과정을 진행한다. 넣을 수 있는 무게도 1부터 최대 무게까지의 상황을 놓고 가정을 시작한다. 결과를 보면 넣을 수 있는 무게가 비로소 6이 되었을 때 첫번째 물건을 가방에 넣게 되면 가치가 13이 되고 안 넣었을 때보다 가치가 높으므로 해당 무게에서 최대 가치는 13이다.

 

무게	1	2	3	4	5	6	7
1번째 물건	0	0	0	0	0	13	13
2번째 물건	0	0	0	8	8	13	13

 

2번째 물건을 가방에 넣는 과정에서 넣을 수 있는 무게가 6이라고 했을 때, 첫번째 물건때와 동일하게 2번째 물건을 넣었을 때랑 안넣었을때랑 가치를 비교하면 된다. 2번째 물건을 안넣는 다면 무게가 6이 남고 첫번째 물건을 넣으면 가치가 13이 되고 2번째 물건을 넣는 다면 가치가 8이 되고 남은 무게는 2가 된다. 하지만 첫번째 물건의 무게는 6이기에 넣을 경우의 가치는 8이 된다. 따라서 13이 최대 가치가 된다.

 

위 두 상황을 보면 dp[i][j]에서 i번째의 물건을 안넣을 경우와 가방에 i번째 물건을 넣을 수 있는 경우 넣었을 때 가치를 비교해야 한다.
i번째 물건을 안넣을 경우 가치는 어떻게 알 수 있을 까? 해답은 i번째 물건을 제외한 0부터 i - 1 물건들을 고려했을 때 최대 가치가 저장된 dp[i - 1][j]가 된다.

           dp[i][j] = dp[i - 1][j]; //i번째 물건을 안넣을 경우의 최대 가치
                if (j - objects[i][0] >= 0) {
                    int value = dp[i - 1][j - objects[i][0]] + objects[i][1]; //넣을 경우 최대 가치
                    dp[i][j] = Math.max(value, dp[i][j]);

                }

위 과정을 반복문으로 진행하게 되면 모든 경우의 최대 가치는 dp[물건의 갯수][최대 무게]에 저장 되어 있다.

 

전체 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int maxWeight = scanner.nextInt();

        int[][] objects = new int[n + 1][2];
        int[][] dp = new int[n + 1][maxWeight + 1]; // i - 1을 반복문에서 비교하기 때문에 -1을 방지하기 위해 n + 1까지 배열을 할당

        for (int index = 1; index <= n; index++) {
            objects[index][0] = scanner.nextInt(); //무게
            objects[index][1] = scanner.nextInt(); //가치
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= maxWeight; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - objects[i][0] >= 0) {
                    int value = dp[i - 1][j - objects[i][0]] + objects[i][1];
                    dp[i][j] = Math.max(value, dp[i][j]);

                }
            }
        }

        System.out.println(dp[n][maxWeight]);
    }
}

 

참고

• 냅색 알고리즘