평범한 배낭 ( 백준 12865 )

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

* 잘 알려진 WellKnown 문제.

* 포스팅한 문제중 카드 구매하기 문제와 비슷한 유형이다.

* 카드 구매하기의 dp[] 배열의 의미는 

dp[i] : i개의 카드팩을 구매 하기위한 최대 금액

* 평범한 배낭 문제의 dp[][] 배열의 의미는

dp[i][w] : i개의 물건을 고려했을때 무게 w가 가지는 최대 가치 ( value )

* 두 문제의 차이점은

- 카드팩은 i개의 카드팩을 구매하기 위한 금액 2가지의 변수가 존재하지만

- 평범한 배낭은 i개의 물건을 고려하기 위한 w무게의 가치 즉 3가지의 변수를 고려해야한다.

 

- 현재 무게값을 빼고 새로운 가치를 더한다

- (현재 물건갯수 -1)와 같은 무게값과 비교해서 더 큰값을 갱신.

 

* 카드팩 구매하기 점화식을 리마인드 해보면

dp[i] = Math.max(dp[i], d[i-j]+pack[j]);

 

* 따라서 평범한 배낭의 점화식을 아래와 같이 작성할 수 있다.

dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w-weight[i] + value[i]);

 

- 즉 위와 같은 점화식은 i개를 고려했을때의 최댓값(최적해)을 고려하는 점화식이다.

 

import java.io.*;
import java.util.*;

public class BOJ12865 {
    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());

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

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

        for(int i = 1; i <= N; i++) {
            for(int w = 0; w <= K; w++) {
                if(w < weights[i]) {
                    dp[i][w] = dp[i-1][w];
                }
                else {
                    dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w-weights[i]] + values[i]);
                }
            }
        }

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

 

* 위와 같이 코드로 구현할 수 있다.

* 무게가 담을 수 없을때는 (현재 물건 갯수 -1) 한값으로 갱신하는 예외 처리를 추가해야한다