백준 12865 평범한 배낭 JAVA (knapsack problem, 배낭문제, DP)

1. 문제

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

2. 설명

Knapsack Problem 알고리즘이라고 유명한 DP 문제이다.

점화식은 아래와 같다.

weight[i]<=j 일 때, dp[i][j] = Math.max(value[i]+dp[i-1][j-weight[i]], dp[i-1][j]) 라는 것

weight[i]>j 일 때는 dp[i][j] = dp[i-1][j] 이다.

 

3. 코드

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

public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 물품의 수
		int K = Integer.parseInt(st.nextToken()); // 준서가 버틸 수 있는 무게
		int[][] dp = new int[N+1][K+1];
		
		int[] weight = new int[N];
		int[] value = new int[N];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			weight[i] = Integer.parseInt(st.nextToken()); // 무게
			value[i] = Integer.parseInt(st.nextToken()); // 가치
		}
		
		int max = 0;
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=K; j++) {
				if(weight[i-1]<=j)
					dp[i][j] = Math.max(value[i-1]+dp[i-1][j-weight[i-1]], dp[i-1][j]);
				else
					dp[i][j] = dp[i-1][j];
				max = Math.max(dp[i][j], max);
			}
		}
		System.out.println(max);
	}
}