[백준 알고리즘] 12865번: 평범한 배낭 (Java / 자바)

기본 knapsack 문제이다. 

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

public class boj_12865 {
	static int N, K, A;
	static int dp[][];
	static int items[][];
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		items = new int[N][2];
		for (int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			items[i][0] = Integer.parseInt(st.nextToken());  // 무게
			items[i][1] = Integer.parseInt(st.nextToken());  // 가치
		}
		
		// dp 테이블 초기화
		dp = new int[N+1][K+1];
		
		for (int i=1; i<=N; i++) {
			for (int w=1; w<=K; w++) {
				// 1. 현재 물건이 현재 용량보다 높은 경우.. 안넣기 (w는 남아있는 배낭의 무게한도를 의미함)
				if (items[i-1][0] > w) dp[i][w] = dp[i-1][w];
				// 2. 무게 안넘어감
				else {
					dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w-items[i-1][0]] + items[i-1][1]);
					// 안넣는 경우 or 넣는 경우 중 최대
				}
			}
		}
		
		System.out.println(dp[N][K]);
	}
}

 

if (items[i-1][0] > w) dp[i][w] = dp[i-1][w];

헷갈린 부분은 현재 물건이 용량을 넘는지 체크할 때 , w(현재 용량)을 넘는지 체크해야하는 것이다.

배낭 무게가 10이라면

배낭 무게가 1일때, 2일때, ... , 10일때 (w일때) 각각의 부분 문제 내에서

최적값을 구해서 w+1에서 w에서 구한 값을 참고해서 최적값을 구한다.

배낭 무게가 w라면 w를 넘는 물건은 넣을 수 없고, 넣을 수 있는 물건들 중에서 넣는 경우와 안넣는 경우 두 가지중에 최선을 선택하면 된다.