[백준 15188] Packing - JAVA

문제 링크 : https://www.acmicpc.net/problem/15188

문제 정의

• $N$ 개의 선물 존재
• 선물을 들고 갈 수 있는 드론 2개 존재
  • 각 드론의 무게 제한 W1 W2
• 선물의 무게 배열 w 제공
• 선물의 가치 배열 v 제공
• 두 드론이 들고갈 수 있는 선물의 최대 가치 구하기

---

접근 방법

일반적인 냅색 문제와는 다르다

기존 문제

일반적인 냅색 문제는 하나의 가방을 사용하므로
냅색 문제를 푸는 다이나믹 프로그래밍 기법으로 최대 가치만을 출력합니다.

해당 문제

세 가지 고민 거리가 존재합니다.

• 드론이 한 대가 아닌 두 대인데 어떻게 항상 최적해를 찾지?
• 어떻게 이전 드론에 선택된 선물을 다른 드론에서 선택하지 않도록 처리하지?
• 선택된 선물을 어떻게 파악해서 중복 적재를 피하지?

세 가지 고민을 분리해서 해결해보겠습니다.

---

최적해 찾기

처음 이 문제를 보고 든 생각은

• 가치가 높은 어떤 선물이 두 드론에 모두 적재 가능하다면 어떤 드론에 적재되도록 해야되지?
• 위와 같은 선물이 여러 개라면 어떻게 항상 최적해임을 보장하도록 하지?

와 같은 생각을 했습니다.

정답은 간단했습니다.

드론의 적재 무게가 적은 드론부터 냅색 알고리즘을 수행하는 것입니다.

적재 용량이 적은 드론부터 냅색 알고리즘을 수행한다면,
상대적으로 선택의 폭이 좁은 자원(작은 드론)에게
꼭 필요한 물건을 먼저 배정할 수 있게 됩니다.

만약 용량이 큰 드론부터 물건을 채우게 되면,
적재 무게가 적은 드론에도 충분히 들어갈 수 있는 가벼운 물건들을
큰 드론이 미리 선점해 버릴 수 있습니다.

이 경우 정작 작은 드론은 남은 물건들 중 자신의 용량에 맞는 것이 없어 공간을 낭비하게 되고,
결과적으로 전체 가치의 합이 낮아질 가능성이 있어 항상 최적해가 되지 못합니다.

---

선물 중복 적재 문제

다음은 선물 중복 적재입니다.

선물을 중복 적재하지 않으려면
첫 번째 드론에 적재한 선물을
두 번째 드론에서 선택하지 못하게 해야합니다.

해당 드론이 냅색을 수행할 때 적재한 선물의 가치를 0으로 변경해서
다음 드론이 냅색을 수행할 때 해당 선물을 선택하지 못하게 막아야 합니다.

그렇다면 해당 드론이 적재한 선물이 어떤 것인지 어떻게 파악할까?

그 해답을 아래 내용에서 찾아보겠습니다.

---

냅색 알고리즘에서 선택된 선물 찾기

최대 가치만 구하는 1차원 DP 배열은 공간 효율적이지만,
"어떤 선물을 담았는지" 알 수 없다는 단점이 있습니다.

그래서 저는 역추적이 가능한 2차원 DP 배열($dp[N+1][W+1]$)을 선택했습니다.

역추적 방법은 의외로 간단합니다.
테이블의 가장 우측 하단인 $dp[N][W]$에서 시작하여
위쪽 행($dp[N-1][W]$)과 값을 비교하며 거꾸로 올라가는 것입니다.

• dp[i][w] == dp[i-1][w] 인 경우:
  • $i$번째 선물을 넣지 않아도 이전까지의 최대 가치와 동일하다는 뜻입니다.
  • 즉, 이 선물은 선택되지 않았습니다.
  • 무게 $w$를 유지한 채 $i-1$행으로 이동합니다.
• dp[i][w] != dp[i-1][w] 인 경우:
  • $i$번째 선물을 넣었기 때문에 가치가 변했다는 증거입니다.
  • 즉, 이 선물은 적재되었습니다.
  • 결과 리스트에 담고, 현재 무게 $w$에서 해당 선물의 무게를 뺀 뒤 $i-1$행으로 이동합니다.

---

정리

다중 냅색 문제에서는 세 가지 원리가 중요합니다.

• 최적해를 보장하도록 적은 무게부터 냅색 알고리즘 수행
• 물건(선물)이 중복 처리되지 않도록 선택된 물건(선물)은 제외 처리
• 냅색에서 선택된 물건(선물)을 찾는 역추적 로직
  • 역추적을 위해 항상 dp는 2차원 배열로 선언

---

코드

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


public class Main {
	static StringTokenizer st;
	static int N;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int P = Integer.parseInt(br.readLine());

		for (int T = 1; T <= P; T++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			int W1 = Integer.parseInt(st.nextToken());
			int W2 = Integer.parseInt(st.nextToken());
			int[] w = new int[N+1];
			int[] v = new int[N+1];

			st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= N; i++) {
				w[i] = Integer.parseInt(st.nextToken());
			}

			st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= N; i++) {
				v[i] = Integer.parseInt(st.nextToken());
			}

			if (W1 > W2) {
				int tmp = W1;
				W1 = W2;
				W2 = tmp;
			}

			int value = 0;

			value += knapsack(N, W1, w, v);
			value += knapsack(N, W2, w, v);

			sb.append("Problem ").append(T).append(": ").append(value).append("\n");
		}

		System.out.println(sb);
	}

	static int knapsack(int N, int W, int[] w, int[] v) {
		int[][] dp = new int[N+1][W+1];

		for (int i = 1; i <= N; i++) {
			if (v[i] <= 0 || w[i] > W) {
				System.arraycopy(dp[i - 1], 0, dp[i], 0, W+1);
				continue;
			}

			for (int j = W; j >= w[i]; j--) {
				dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
			}

            if (w[i] >= 0) System.arraycopy(dp[i - 1], 0, dp[i], 0, w[i]);
		}

		tracing(dp, W, w, v);

		return dp[N][W];
	}

	private static void tracing(int[][] dp, int W, int[] w, int[] v) {
		int index = N;

		while (index > 0 && W > 0) {
			if (dp[index][W] != dp[index-1][W]) {
				W -= w[index];
				v[index] = 0;
			}
			index--;
		}
	}
}