[백준/boj] 12865: 평범한 배낭 (Java) / DP / 배낭 문제

문제

12865번: 평범한 배낭

설명

import java.util.*;
import java.io.*;

public class Main_BOJ_12865_평범한배낭 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] dp;
	static int N, K;

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		dp = new int[N + 1][K + 1];
		int w, v;
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			w = Integer.parseInt(st.nextToken());
			v = Integer.parseInt(st.nextToken());
			for (int j = 1; j <= K; j++) {
				dp[i][j] = j < w ? dp[i-1][j] : Math.max(v + dp[i - 1][j - w], dp[i - 1][j]);
			}
		}
		System.out.println(dp[N][K]);
	}
}

i( 1 <= i <= N)번째 가방까지 있다고 가정하면서 무게j 일때 담을 수 있는 최대 가치값을 dp 배열에 담는다.

변수 설명

• dp[i][j] (int) : i번째 가방까지 살펴봤을 때, j 무게일 때 담을 수 있는 물건들의 최대 합
• N (int) : 물건의 갯수
• K (int) : 가방에 담을 수 있는 물건들의 무게 합
• w (int) : i 번째 물건의 무게
• v (int) : i 번째 물건의 가치
• i (int) : i 번째 물건까지 있다고 가정한다. (예를 들어, i = 2 이면 첫째줄 물건과 둘째줄 물건이 있을 때 담을 수 있는 최대 가치값을 dp[i][]에 담는다.)
• j (int) : 현재 담을 수 있는 무게 (1 부터 K까지)

풀이

항상 현재 무게(j)에서 담을 수 있는 최대 가치 값을 dp 배열에 저장한다.

완성된 dp 배열 (0행과 0열은 편의상 그리지 않음)

for (int j = 1; j <= K; j++) {
	dp[i][j] = j < w ? dp[i-1][j] : Math.max(v + dp[i - 1][j - w], dp[i - 1][j]);
}

1. dp[i][j] 에서 j 가 w 보다 가벼울 때는 i번째 물건을 가방에 담을 수 없으므로 이전 dp의 가치를 그대로 할당한다 (이전 행에는 j 무게일 때 담은 물건들의 최대 가치 값이 할당되어 있다)

2. dp[i][j] 에서 j 가 w와 같거나 무거울 때는 n번째 물건을 담을 수 있다. 이때, j = j- n + n 임을 생각하자

• n번째 물건의 가치값(v) +  이전 행의 j-n번 열의 가치값 (dp[i-1][j-n]) 이 이전 행에서 j무게 일 때 담은 물건의 최대 가치값(dp[i-1][j]) 보다 크다면 같은 무게에 더 큰 가치를 담을 수 있으므로  dp[i][j] = v + dp[i-1][j-n] 이 된다.
• v + dp[i-1][j-n]이 dp[i-1][j] 보다 작거나 같다면 dp[i-1][j] 를 그대로 dp[i][j]에 할당한다.

3. dp가 완성되면 dp[N][K] 는 N번째 가방까지 있다고 가정했을 때, K 무게 이하에서 담을 수 있는 물건의 최대 가치 값이 되므로 답이된다.