[Baekjoon] 12865 평범한 배낭 문제

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

 

배낭 문제는 냅색 알고리즘의 대표 문제라고 할 수 있다. 냅색 알고리즘은 다이나믹 프로그래밍에 속하는 알고리즘이다.

 

문제의 입력 예제를 통해 냅색 알고리즘에 대해 알아보자. 

1. 먼저 넣을 수 있는 무게 크기만큼 1차원 배열을 하나 준비하자. (dy라고 하겠다)

2. 첫 번째 경우(4kg, 8원) 4kg의 가방에 8원의 가치를 가진 물건을 하나 넣을 수 있다. 5 - 7까지 모두 동일하다.

3. 두 번째 경우(5kg, 6원) 5kg의 가방에 6원의 가치를 가진 물건을 넣을 수는 있지만 이전 값인 8이 더 크므로 4kg, 8원짜리 물건을 넣는다. 

 

 

4. 세 번째 경우(3kg, 2원)

  -> 3kg의 가방에 2원짜리 물건을 넣을 수 있다. 

  -> 4kg -6kg 의 가방에 넣을 수는 있지만 이전의 값들이 더 크다.

  -> 7kg의 가방에는 3kg와 4kg 물건을 각각 한 개씩 넣어서 10원의 가치르 가진 가방을 만들 수 있다. 

  -> 여기서 7원의 값이 변경되는 코드는 다음과 같다. (a[j-w] + v > a[j])

 

이 알고리즘을 적용해서 이 문제를 풀면 오답이 나온다. 이유는 다음과 같다.

1kg, 10원의 가치를 가진 물건이 있다고 할 때 다음과 같이 a[j-w] + v > a[j]를 이용하면 1kg, 10원의 물건은 하나 밖에 없는데 이를 여러번 가방에 넣은 꼴이 되어 버린다. 

 

따라서 이 문제를 해결하기 위해 7kg 가방부터 거꾸로 알고리즘을 적용시킨다.

import java.util.Scanner;

public class Main {

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

        int n = sc.nextInt(); // 물품의 수
        int k = sc.nextInt(); // 준서가 버티는 무게
        int[] bag = new int[k+1];

        for(int i = 0; i < n; i++) {
            int w = sc.nextInt();
            int v = sc.nextInt();
            for(int j = k; j >= w; j--) {
                bag[j] = Math.max(bag[j], v + bag[j-w]);
            }
        }

        System.out.println(bag[k]);
    }
}