냅색 ( Knapsack )

냅색 알고리즘은 배낭 알고리즘이라도고 불리며,
주어진 가방에 최대한 가치가 큰 물건을 담는 문제이다.

냅색은 유한 냅색, 무한 냅색 문제로 나뉜다.

• 유한 냅색 문제

  • 각 물건은 하나씩만 존재하며, 가방에 담거나 담지 않을 수 있다.

  이 문제를 해결하기 위해서는 동적 계획법 ( DP ) 을 이용한다.
  물건의 무게와 가치를 저장하는 class를 DP에 채워나가며
  각 칸에는 해당 물건을 포함하는 경우와 포함하지 않는 경우의 최대 가치를 저장한다.

  유한 냅색은 역순으로 DP[] 를 채워나간다.

• 무한 냅색 문제

  • 각 물건은 무한히 존재하며, 가방에 담을 수 있는 최대 가치를 구한다.

  이 문제를 해결하기 위해서는 탐욕 알고리즘 (Greedy)을 이용한다.
  유한 냅색과 달리 각 물건을 무한히 선택할 수 있기 때문에,
  해당 물건을 선택하지 않을 경우를 고려하지 않는다.

  물건을 추가할 때,
  기존의 값보다 새로 들어올 값이 더 작을 경우에만 dp 배열을 초기화 시켜준다.

  무한 냅색은 정방향으로 DP[]를 채워나간다.

유한 냅색 예제
[백준] 평범한 배낭

-  Java Code

	public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 물품의 수
        int N = Integer.parseInt(st.nextToken());
        // 가방이 버틸 수 있는 무게
        int K = Integer.parseInt(st.nextToken());

        Item item[] = new Item[N];
        for (int i = 0; i < item.length; i++) {
            st = new StringTokenizer(br.readLine());
            int weight = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            item[i] = new Item(weight, value);
        }

        int DP[] = new int[K + 1];
        for (int i = 0; i < item.length; i++) {

            int curr_weight = item[i].weight;
            int curr_value = item[i].value;

            // 유한 냅색 알고리즘은 역순으로 DP 배열을 채워나가야함
            for (int j = K; j >= curr_weight; j--) {
                DP[j] = Math.max(DP[j - curr_weight] + curr_value, DP[j]);
            }

        }

        System.out.println(DP[K]);

    }

    static class Item {
        int weight;
        int value;

        Item(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }

무한 냅색 예제

	다음과 같이 여러 단위의 동전들이 주어져 있을 때
    거스름돈으로 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?
    각 단위의 동전은 ★무한정 쓸 수 있다

-  Java Code

	public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 동전의 종류
        int N = Integer.parseInt(br.readLine());

        // 동전의 value 가 작은 값부터 채워넣어야함
        PriorityQueue<Integer> coin = new PriorityQueue<>();

        // 코인 입력
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            coin.add(Integer.parseInt(st.nextToken()));
        }

        // 주어지는 금액
        int target = Integer.parseInt(br.readLine());

        int dp[] = new int[target + 1];

        while (!coin.isEmpty()) {

            int curCoin = coin.poll();
            for (int i = curCoin; i < dp.length; i++) {
                // 점화식
                dp[i] = dp[i - curCoin] + 1;
            }

        }

        System.out.println(dp[target]);


    }

 	- input -
    3
    1 2 5
    15

    - output -
    3
    
    why? 5, 5, 5 = 3