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

 

 

 

dp[N+1][K+1]

 

행을 증가시키면서 값을 누적시켜 최적 무게를 계산한다.

dp의 열 값은 해당 무게만큼 물건을 넣었을 때 가치의 최댓값이다.

 

 

 

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());

        Bag[] arr = new Bag[N + 1];

        for(int i=1; i<N+1; i++){
            st = new StringTokenizer(br.readLine());
            arr[i] = new Bag(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        int[][] dp = new int[N + 1][K + 1];

        for(int i=1; i<N+1; i++){
            for(int j=1; j<K+1; j++){
                
                if(arr[i].weight > j){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - arr[i].weight] + arr[i].value);
                }

            }
        }

        System.out.println(dp[N][K]);

        for(int i=1; i<N+1; i++){
            for(int j=1; j<K+1; j++){
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        

    }
}

class Bag{
    int weight, value;

    Bag(int weight, int value){
        this.weight = weight;
        this.value = value;
    }
    
}

 

 

dp 배열 디자인 / 점화식 찾기 공부하기..