[JAVA/백준] 동적 계획법 1: 평범한 배낭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.Scanner;

/**
 * 
 * @author HEESOO
 *
 */
public class Main {
	public static void main(String[] args){
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		int k=input.nextInt();
		int[] w=new int[n+1];
		int[] v=new int[n+1];
		for(int i=1;i<=n;i++){
			w[i]=input.nextInt();
			v[i]=input.nextInt();
		}
		
		int[][] dp=new int[n+1][k+1];
		for(int i=1;i<=n;i++){
			for(int j=1;j<=k;j++){
				dp[i][j]=dp[i-1][j];
				if(j-w[i]>=0){
					dp[i][j]=Math.max(dp[i][j],  dp[i-1][j-w[i]]+v[i]);
				}
			}
		}
		
		System.out.println(dp[n][k]);
	}
}