[백준] 평범한 배낭 12865 - JAVA

문제

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

12865번: 평범한 배낭

 

knapsack 알고리즘을 사용하는 문제였다.

https://st-lab.tistory.com/141 를 보고 알고리즘을 이해할 수 있었다.

 

코드

import java.io.*;
import java.util.*;

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 weight [] = new int [n+1];
		int value [] = new int [n+1];
		
		for(int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			int w = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());	
			
			weight[i] = w;
			value[i] = v;
		
		}
		
		int dp [][] = new int [n+1][k+1];
		
		for(int w = 1; w <= k; w++) {
			for(int i = 1; i <= n; i++) {
				dp[i][w] = dp[i-1][w];
				if(w - weight[i] >= 0) {
					dp[i][w] = Math.max(dp[i][w], value[i] + dp[i-1][w-weight[i]]);
				}
			}
		}
		
		System.out.print(dp[n][k]);
		
		
	}

}