[BOJ] - 평범한 배낭 / 12865번 (Java)

[BOJ] - 평범한 배낭 / 12865번 (Java)

[BOJ] - 평범한 배낭 / 12865번 (Java)

1. 문제 접근

DP를 적용하는 0/1 Knapsack 문제의 대표 문제 유형이다.

 

물품에는 2개의 요소가 있다 (`부피`, `가치`)

 

둘 중 부피를 기준으로 2차원 동적 테이블을 생성한다.

 

동적 테이블의 정의는 다음과 같다.

dpTable[item][volume]: 부피 volume을 만족하는 item을 포함하는 최대 가치 

 

0번 물품부터 N-1번 물품까지 탐색하며, 각 물품을 포함하며 얻을 수 있는 최대 가치를 구하면 된다.

 

2가지 경우가 존재한다.

1. 물품을 넣을 수 없는 경우
2. 물품을 넣을 수 있는 경우

먼저 물품을 넣을 수 없는 경우는 현재 물품의 부피가 고려 중인 부피보다 큰 경우이다. 

 

따라서 물품을 넣을 수 없는 경우, 이전 물품까지 고려한 최대 가치를 그대로 가져온다.

// 넣을 수 없는 경우
if (col < currItem.weight) {
    dpTable[idx][col] = dpTable[idx - 1][col];
}

다음으로 넣을 수 있는 경우다.

 

넣을 수 있을 경우 역시 2가지로 나누어진다.

1. 물품을 넣는 것이 이득인 경우
2. 물품을 넣지 않는 것이 이득인 경우

따라서 두 경우를 비교하여 큰 값으로 갱신하면된다.

 

물품을 넣는 경우, 이전 물품을 고려한 최적해에 대해 현재 물품의 부피만큼을 차감한 최적해를 사용하게 된다.

// 넣을 수 있는 경우
else {
    // 넣는다 vs 안 넣는다
    dpTable[idx][col] = 
            Math.max(dpTable[idx - 1][col],
                    dpTable[idx - 1][col - currItem.weight] + currItem.value);
}

최종적으로 모든 물품을 고려한 뒤, 최대 부피의 동적 테이블 값이 답이 된다.

---

2. 코드

package boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * [BOJ] - 평범한 배낭 / 12865번
 * @author JinHxxxxKim
 * 
 * 0-1 Knapsack 문제
 * 
 * 1. 모든 물품을 순회하며 경우의 수를 확인한다.
 * 2. 총 2가지의 경우의 수가 존재한다.
 * 	2-1. 물품을 넣을 수 있는 경우(현재 확인 중인 무게보다 작을 경우)
 * 	 2-1-1. 넣는다: dp[idx-1][col-currWeight] + currValue
 * 	 2-1-2. 안 넣는다: dp[idx-1][col]
 * 	  => 두 경우의 수 중 큰 것을 선택한다.
 *  2-2. 물품을 넣을 수 없는 경우(현재 확인 중인 무게보다 클 경우)
 *    2-2-1. 안 넣는다: dp[idx-1][col]
 * 3. 최종적으로 dp[N][K]를 출력한다.
 */
public class Solution {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	private static StringTokenizer st;
	
	static int[][] dpTable;
	static Item[] items;
	static int N, K;
	
	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine().trim());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		items = new Item[N];
		
		// dp테이블 초기화
		dpTable = new int[N + 1][K + 1];
		// 0열 초기화
		for (int idx = 0; idx < N + 1; ++idx) {
			dpTable[idx][0] = 0;
		}
		// 0행 초기화
		for (int idx = 0; idx < K + 1; ++idx) {
			dpTable[0][idx] = 0;
		}
		
		// Item 입력 받기
		for(int cnt = 0; cnt<N;++cnt) {
			st = new StringTokenizer(br.readLine().trim());
			items[cnt] = new Item(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		
		// dp 로직 시작
		// 모든 item 순회하며 조회
		for (int idx = 1; idx < N + 1; ++idx) {
			Item currItem = items[idx - 1];
			for (int col = 1; col < K + 1; ++col) {
				// 넣을 수 없는 경우
				if (col < currItem.weight) {
					dpTable[idx][col] = dpTable[idx - 1][col];
				}
				// 넣을 수 있는 경우
				else {
					// 넣는다 vs 안 넣는다
					dpTable[idx][col] = 
							Math.max(dpTable[idx - 1][col],
									dpTable[idx - 1][col - currItem.weight] + currItem.value);
				}
			}
		}
		System.out.println(dpTable[N][K]);
	}

	// 물품 클래스
	static class Item {
		int weight, value;

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

---

3. 디버깅

동적 테이블의 열 값이 되는 부피의 경우 0 이상 최대 부피 이하를 모두 고려해야한다.

 

따라서 행, 열에 각각 padding을 추가해준다.

 

즉, "부피가 0 일 때 최대 가치"와 "물품을 넣지 않을 때 부피"가 되는데, 이들은 모두 0이므로 0으로 초기화 해주면 된다.

---

4. 결과