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

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

12865번: 평범한 배낭

문제

풀이

KnapSack 이라는 굉장히 유명한 다이나믹 프로그래밍 유형의 문제이다.

 

그리디 접근이 왜 안되는가 .. ?

가방에 넣는 순서를 무게순 혹은 가치순이라고 가정을 해보면  

1. 무게순으로 일단 넣어서 무게합이 11이 되고, 가치합이 12가 되었다. 그런데 바로 뒤에 무게11짜리 가치 100짜리가 있는 경우가 생겨버렸다.  => 실패

혹은

2. 가치순으로 넣어서 가치 12 무게 13 이 되었는데 , 바로 뒤에 무게 대비 가치가 좋은 물건이 있었다. => 실패

 

결국엔 모든 경우의수를 다 따져봐야한다. 

가령 물건이 A,B,C,D 가 있다고 했을때 각각의 물건이 있거나 없거나로 따져봐야 한다는 것이다. 하지만

시간복잡도는 2^(물건의갯수) , 즉 => O(2^n) 라는 지수시간 복잡도 발생 

 

그래서 부분적으로 중복되는부분을 찾아 최적화시켜야 하므로 다이나믹프로그래밍 유형이다.

따져봐야 하는 경우는 두 가지이다. => 1. 물건의 갯수 2. 무게따라서 DP배열의 크기를 DP[물건의갯수][최대무게] 로 할 수 있다.

 

(i번째 물건이 포함되었을경우 와 아닌경우) x ( 1 ~ 최대무게(K) ) 로 하면  (1<=j<=K) 

1. dp[i][j] = Max( dp[i-1][j] , dp[i-1][ j- i번째 물건의 무게] + i번째 물건의 가치 )

2. dp[i][j]j = dp[i-1][j] 

두 가지 점화식으로 나타 낼 수 있다.

 

 

 

import java.util.*;
import java.io.*;
 
public class Main{
 
    static int N,K;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]); K = Integer.parseInt(input[1]);
        int[][] dp = new int[N+1][K+1];
        int[][] arr = new int[N+1][2];
        for(int i=1;i<=N;i++)
             arr[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
 
        for(int i=1;i<=N;i++){
            for(int j=1;j<=K;j++){
                if(arr[i][0] <= j)
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-arr[i][0]]+arr[i][1]);//13,
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
        System.out.println(dp[N][K]);
    }
}