백준 12865번

원본 : www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {

	public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void main(String[] args) throws Exception {
		String str = reader.readLine();
		int n = Integer.parseInt(str.split(" ")[0]);
		int k = Integer.parseInt(str.split(" ")[1]);
		
		ArrayList<Integer> w = new ArrayList<>();
		ArrayList<Integer> v = new ArrayList<>();
		w.add(0);
		v.add(0);
		
		for (int i = 0; i < n; i++) {
			String item = reader.readLine();
			w.add(Integer.parseInt(item.split(" ")[0]));
			v.add(Integer.parseInt(item.split(" ")[1]));
		}
		
		int dp[][] = new int[n + 1][k + 1];
		
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= k; j++) {
				if (i == 0) {
					dp[i][j] = 0;
				} else if (j == 0) {
					dp[i][j] = 0;
				} else {
					int maxValue = dp[i - 1][j];
					if (j - w.get(i) >= 0) {
						maxValue = maxValue(dp[i - 1][j], dp[i - 1][j - w.get(i)] + v.get(i));
					}
					
					dp[i][j] = maxValue;
				}
			}
		}
		
		writer.write(dp[n][k] + "");
		
		writer.flush();
	}
	
	public static int maxValue(int a, int b) {
		if (a >= b) {
			return a;
		} else {
			return b;
		}
	}
	
}