냅색(Napsack) 문제(DP)

냅색(Napsack) 문제는 DP 알고리즘을 활용하여 해결할 수 있는 대표적인 문제 중 하나입니다. 이 문제는 무게와 가치가 각각 다른 여러 개의 물건이 있을 때, 주어진 가방의 용량을 초과하지 않으면서 가치의 합을 최대로 하는 물건들의 조합을 찾는 문제입니다.

냅색 문제는 0/1 냅색과 무한 냅색으로 나누어집니다. 0/1 냅색은 각 물건을 하나만 선택할 수 있으며, 무한 냅색은 각 물건을 여러 번 선택할 수 있습니다.

0/1 냅색 문제를 예로 들면, 물건의 종류가 n개이고, 각 물건의 무게와 가치가 w와 v로 주어질 때, 가방의 용량이 W일 때, 최대 가치를 구하는 문제입니다.

이 문제를 DP로 해결하기 위해서는 물건의 종류와 가방의 용량을 하나의 축으로 하는 2차원 배열을 선언하고, 해당 배열을 채워가면서 최적해를 찾아갑니다. 물건을 선택할 수 있는 경우와 선택할 수 없는 경우를 각각 고려하여 점화식을 세우고, 이를 활용하여 문제를 해결합니다.

 

예를 들어, 0/1 냅색 문제에서 다음과 같은 입력이 주어졌다고 가정해봅시다.

  - 물건의 종류 : 4
  - 물건의 무게 : 5kg, 3kg, 4kg, 2kg
  - 물건의 가치 : 10, 7, 9, 6
  - 가방의 용량 : 8kg
이 경우, 가방에 담을 수 있는 물건들의 조합 중에서 가치의 합이 최대가 되는 조합을 찾아야 합니다. 이를 DP로 해결하기 위해서는 다음과 같은 절차를 따릅니다.

  1. 2차원 배열을 초기화합니다. 이 때, 배열의 크기는 물건의 종류+1 x 가방의 용량+1 입니다.
  2. 2차원 배열을 채워가면서 최적해를 찾아갑니다. 물건을 선택할 수 있는 경우와 선택할 수 없는 경우를 고려하여 점화식을 세우고, 이를 활용하여 배열을 채워갑니다.
  3. 마지막으로 배열의 마지막 항목에 저장된 최적해를 출력합니다.

위 예시에서는 다음과 같은 2차원 배열을 선언할 수 있습니다.

  - arr[i][j] : i번째 물건까지 고려했을 때, 가방의 용량이 j일 때 선택할 수 있는 물건들의 가치 합의 최댓값
이 배열은 다음과 같이 초기화할 수 있습니다.

  - arr[0][j] = 0 (0번째 물건을 고려하지 않은 경우 가치 합은 0입니다.)
  - arr[i][0] = 0 (가방의 용량이 0인 경우 가치 합은 0입니다.)
이제 물건을 하나씩 선택해가면서 배열을 채워나갑니다. 물건 i를 선택할 수 있는 경우와 선택할 수 없는 경우를 각각 고려하여 점화식을 세워봅시다.

  - 물건 i를 선택할 수 있는 경우 : arr[i][j] = arr[i-1][j-w[i]] + v[i]
  - 물건 i를 선택할 수 없는 경우 : arr[i][j] = arr[i-1][j]
위의 점화식에서 w[i]는 물건 i의 무게, v[i]는 물건 i의 가치를 나타냅니다. 따라서 물건 1부터 차례대로 선택해가면서 배열을 채워나가면 최종적으로 arr[4][8]에 저장된 값이 최적해가 됩니다.

	행/열	0	1	2	3	4	5	6	7	8
무게 / 가치	0	0	0	0	0	0	0	0	0	0
5 / 10	1	0	0	0	0	0	10	10	10	10
3 / 7	2	0	0	0	7	7	10	10	10	17
4 / 9	3	0	0	0	7	9	10	10	16	17
2 / 6	4	0	0	6	7	9	13	15	16	17

0/1 냅색 코드

import java.util.*;

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

        // 입력 받기
        int n = scanner.nextInt(); // 물건의 종류 수
        int[] w = new int[n+1]; // 물건의 무게
        int[] v = new int[n+1]; // 물건의 가치
        int W = scanner.nextInt(); // 가방의 용량

        for (int i = 1; i <= n; i++) {
            w[i] = scanner.nextInt();
            v[i] = scanner.nextInt();
        }

        // DP를 위한 2차원 배열 생성 및 초기화
        int[][] arr = new int[n+1][W+1];
        for (int i = 0; i <= n; i++) {
            arr[i][0] = 0; // 가방의 용량이 0일 때 가치는 0
        }
        for (int j = 0; j <= W; j++) {
            arr[0][j] = 0; // 물건이 없을 때 가치는 0
        }

        // DP 수행
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= W; j++) {
                // 물건 i를 선택할 수 있는 경우
                if (j - w[i] >= 0) {
                    arr[i][j] = Math.max(arr[i-1][j], arr[i-1][j-w[i]] + v[i]);
                }
                // 물건 i를 선택할 수 없는 경우
                else {
                    arr[i][j] = arr[i-1][j];
                }
            }
        }

        // 결과 출력
        System.out.println(arr[n][W]);
    }
}

무한 냅색 코드

import java.util.*;

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

        // 입력 받기
        int n = scanner.nextInt(); // 물건의 종류 수
        int[] w = new int[n+1]; // 물건의 무게
        int[] v = new int[n+1]; // 물건의 가치
        int W = scanner.nextInt(); // 가방의 용량

        for (int i = 1; i <= n; i++) {
            w[i] = scanner.nextInt();
            v[i] = scanner.nextInt();
        }

        // DP를 위한 1차원 배열 생성 및 초기화
        int[] arr = new int[W+1];
        for (int i = 1; i <= W; i++) {
            arr[i] = 0; // 가방의 용량이 0일 때 가치는 0
        }

        // DP 수행
        for (int i = 1; i <= n; i++) {
            for (int j = w[i]; j <= W; j++) {
                arr[j] = Math.max(arr[j], arr[j-w[i]] + v[i]);
            }
        }

        // 결과 출력
        System.out.println(arr[W]);
    }
}