240718 평범한 배낭

static int n;
static int k;
static int[] dp;

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String[] input = br.readLine().split(" ");
	n = Integer.parseInt(input[0]);
	k = Integer.parseInt(input[1]);
	dp = new int[k + 1];

	for (int i = 0; i < n; i++) {
		input = br.readLine().split(" ");
		int weight = Integer.parseInt(input[0]);
		int value = Integer.parseInt(input[1]);
		fillKnapsack(weight, value);
	}

	System.out.println(dp[k]);
}

public static void fillKnapsack(int weight, int value) {
	for (int i = k; i >= weight; i--) {
		if (dp[i] < dp[i - weight] + value) {
			dp[i] = dp[i - weight] + value;
		}
	}
}

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