보석 배낭 문제 (Knapsack Problem) - 정확한 무게 조합 찾기

문제

보석의 무게와 가격이 주어졌을 때, 제한된 무게 안에서 최대 가격이 되도록 보석을 담는 문제.
가방에 담을 수 있는 보석의 무게는 최대 20kg이며, 각 보석은 한 개씩만 존재한다.

---

풀이

조건문 설명

j < weights[i]

잔여 무게가 현재 보석의 무게보다 적어 보석을 담을 수 없음을 의미한다.
즉, 현재 보석을 고려하기 전에 가방에 넣을 공간이 부족한 경우를 필터링한다.

dp[i - 1][j - weights[i]] != 0 || j == weights[i] || dp[i - 1][j] != 0

보석을 추가할 수 있는 경우를 체크하는 핵심 조건문이다.

1. dp[i - 1][j - weights[i]] != 0

   • 이전 단계에서 무게 j - weights[i]를 만들 수 있는 경우, 현재 보석을 추가할 수 있음을 의미한다.
   • 즉, 현재 보석을 더했을 때 유효한 조합이 되는지를 확인하는 조건이다.

2. j == weights[i]

   • 현재 보석 하나만을 넣었을 때 정확히 무게 j가 되는 경우를 허용하기 위한 조건이다.
   • 예를 들어, j = 6이고 weights[i] = 6이라면, 해당 보석만으로 정확히 무게 6을 만들 수 있다.

3. dp[i - 1][j] != 0

   • 이전 단계에서 이미 무게 j를 만들 수 있었다면, 그 값을 유지해야 한다.
   • 즉, 현재 보석을 추가하지 않아도 최대 가치를 유지할 수 있음을 의미한다.

조건문의 역할

이 조건문을 사용하면, 정확한 무게 조합이 가능한 경우에만 보석을 추가하도록 제한할 수 있다.
이로 인해 무게 제한을 초과하지 않으면서도, 보석의 조합이 정확하게 일치하는 경우에만 업데이트되는 DP 테이블을 유지할 수 있다.

---

코드

다음은 해당 문제를 해결하는 Java 코드이다.

import java.util.*;

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

		int n = 10; // 보석 개수
		int maxWeight = 20; // 최대 무게
		int[] weights = {0, 2, 6, 2, 3, 4, 5, 4, 6, 7, 10}; // 보석 무게 (1-based index)
		int[] values = {0, 3, 5, 4, 2, 3, 3, 2, 6, 9, 8}; // 보석 가치

		int[][] dp = new int[n + 1][maxWeight + 1];

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= maxWeight; j++) {
				if (j < weights[i]) {
					dp[i][j] = dp[i - 1][j]; // 보석을 담을 수 없음
				}
				else if (dp[i - 1][j - weights[i]] != 0 || j == weights[i] || dp[i - 1][j] != 0) {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
				}
			}
		}

		System.out.print("DP\t");
		for (int j = 0; j <= maxWeight; j++) {
			System.out.print(j + "\t");
		}
		System.out.println();

		for (int i = 1; i <= n; i++) {
			System.out.print(i + "\t");
			for (int j = 0; j <= maxWeight; j++) {
				if (dp[i][j] == 0)
					System.out.print("-\t");
				else
					System.out.print(dp[i][j] + "\t");
			}
			System.out.println();
		}

		sc.close();
	}
}

결과

위 코드를 실행하면 다음과 같은 DP 테이블이 출력된다.
각 행은 1~10번째 보석까지 고려했을 때,
각 열은 현재 가방의 허용 무게(0~20kg)에서의 최대 가격을 의미한다.

DP	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	
1	-	-	3	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	
2	-	-	3	-	-	-	5	-	8	-	-	-	-	-	-	-	-	-	-	-	-	
3	-	-	4	-	7	-	5	-	9	-	12	-	-	-	-	-	-	-	-	-	-	
4	-	-	4	2	7	6	5	9	9	7	12	11	-	14	-	-	-	-	-	-	-	
5	-	-	4	2	7	6	7	9	10	9	12	12	12	14	15	14	-	17	-	-	-	
6	-	-	4	2	7	6	7	9	10	10	12	12	12	14	15	15	15	17	17	18	17	
7	-	-	4	2	7	6	7	9	10	10	12	12	12	14	15	15	15	17	17	18	17	
8	-	-	4	2	7	6	7	9	10	10	13	12	13	15	16	16	18	18	18	20	21	
9	-	-	4	2	7	6	7	9	10	13	13	16	15	16	18	19	19	22	21	22	24	
10	-	-	4	2	7	6	7	9	10	13	13	16	15	16	18	19	19	22	21	22	24