(DP) BOJ 12865: 평범한 배낭

BOJ 12865: 평범한 배낭

import java.util.*;

public class BOJ_12865 {
	static int N, K;
	static int[] W, V, dp;
	
	public static void main(String[] args) {
		input();
		knapsack();
		System.out.println(dp[K]);
	}
	
	public static void input() {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		K = sc.nextInt();
		W = new int[N + 1];
		V = new int[N + 1];
		dp = new int[K + 1]; // dp[i] = j, i무게에서 최대 j가치
		
		for(int i = 1; i <= N; i++) {
			W[i] = sc.nextInt();
			V[i] = sc.nextInt();
		}
	}
	
	public static void knapsack() {
		for(int i = 1; i <= N; i++) {
			for(int j = K; j - W[i] >= 0; j--) {
				dp[j] = Math.max(dp[j], dp[j - W[i]] + V[i]);
			}
		}
	}
}

짐을 쪼갤 수 있으면 그리디
쪼갤 수 없으면 DP