[알고리즘] 백준 - 12865 ( 평범한 배낭 ) / 자바

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {

    static int N = 0;
    static int maxWeight = 0;
    
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        maxWeight = Integer.parseInt(st.nextToken());
        
        
        int dp[][] = new int[N+1][maxWeight+1];
       
        
        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            int Weight = Integer.parseInt(st.nextToken()); // 무게
            int value= Integer.parseInt(st.nextToken()); //가치
            
            //i 는 물건의 갯수 , j 는 무게    
            for(int j=1; j<=maxWeight; j++){
                dp[i][j] = dp[i-1][j];
                //무게가 남으면 추가
                if(j-Weight>=0){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-Weight]+value);

                }
            }
        }

        System.out.print(dp[N][maxWeight]);
    }
}