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

 

사용 알고리즘 : DP

 

dp배열을 2차원으로 받는다 

dp[i][j]

i = i번째 배낭

j = 무게

 

    for(int i=1; i<=n; i++) {
            Node a = bag[i-1];
            int w= a.w;
            int v= a.v;
            for(int j=1; j<=k; j++) {
                dp[i][j] = dp[i-1][j];
                if(j-a.w>=0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-w]+v);
                }
            }
        }
        System.out.println(dp[n][k]);
    }

import java.io.*;
import java.util.*;
public class Main {
    static int n,k;
    static int max = 1;
    static Node bag[];
    static int dp[][];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);    // 물건의수
        k = Integer.parseInt(t[1]);    // 버틸수 있는 무게
        dp = new int[n+1][k+1];
        bag = new Node[n];
        for(int i=0; i<n; i++) {
            String[] tt = br.readLine().split(" ");
            int w = Integer.parseInt(tt[0]);
            int v = Integer.parseInt(tt[1]);    
            bag[i] = new Node(w,v);
        }
        
        for(int i=1; i<=n; i++) {
            Node a = bag[i-1];
            int w= a.w;
            int v= a.v;
            for(int j=1; j<=k; j++) {
                dp[i][j] = dp[i-1][j];
                if(j-a.w>=0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-w]+v);
                }
            }
        }
        System.out.println(dp[n][k]);
    }
}
class Node{
    int w,v;
    Node(int w, int v){
        this.w=w;
        this.v=v;
    }
}