[백준] 12865 평범한 배낭

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

2021-01-07

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main12865 {
    public static int N, K, arr[][], dp[][];
    public static void solve() {
        for(int i = 1; i <= N; i++) { // index
            for(int w = 0; w <= K; w++) { // weight
                if(w-arr[i][0] < 0) dp[i][w] = dp[i-1][w]; // 배낭에 물건을 채울 수 없는경우, 그 전까지의 최대값 가져온다.
                else dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w-arr[i][0]] + arr[i][1]);
                // 이번 물건을 채우지 않는 경우 , 이번 물건을 넣어가는 경우(그 전까지 + 해당 차례 같이)
            }
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        arr = new int[N+1][2];
        dp = new int[N+1][K+1];
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(bf.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken()); // weight
            arr[i][1] = Integer.parseInt(st.nextToken()); // value
        }
        
        solve();
        System.out.println(dp[N][K]);
    }
}
 

 

#문제풀이

0/1 knapsack 문제이다.

 

1. weight와 value를 저장할 2차원 배열을 만들어서 [i][0], [i][1]번째에 각각 저장하였다. 후에 인덱싱을 i-1로 계산해야하는 것이 있어서 편의상 1부터 채워넣었다.

 

2. index는 물품의 개수로 1부터 N까지,  weight는 0부터 K까지 기준으로 잡았다. dp 2차원 배열을 사용하였다. 

 

3. 경우의 수는 

 

  (1) w-arr[i][0] < 0 : 물건을 채울 수 없는 경우로, 그 전까지의 최대값(dp[i-1][w])을 그대로 사용했다.

 

  (2) w-arr[i][0] >= 0 : 물건을 채울 수 있는 경우는 두 가지 방법 중 더 큰 경우를 채택하게 된다. 

      - dp[i-1][w] : 현재 물건을 채우지 않는 경우

      - dp[i-1][w-arr[i][0]]+arr[i][1] : 현재 물건을 채우는 경우\

 

 

+) 예제를 기준으로, dp배열이 다음과 같이 채워질 수 있다. 

N = 4, K = 7

index	weight	value
1	6	13
2	4	8
3	3	6
4	5	12

dp 배열

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4	0	0	0	6	8	12	13	14