[백준 12865] 평범한 배낭

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

12865번: 평범한 배낭

 

 

 

대표적인 0-1 knapsack 문제이다.

https://kikikiwiii10.tistory.com/86

knapsack problem

 

 

 

문제에서 주어진 테스트케이스에 대하여 가로 K+1(무게), 세로 N+1(물건 수) 인 표를 만들어서 가질 수 있는 최대 가치를 생각해 보면 다음과 같다.

 

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

 

(+

위의 케이스에서의 최대값은 14이며,

4행 8열에서의 값(14)은

무게가 7이고 2번째 물건까지를 고려했을 때 가질 수 있는 최대 가치(3행 8열) 13을,

3번째 물건이 배낭 안에 담긴 후 남은 무게(4)로 가질 수 있는 최대 가치(3행 5열)을 3번째 물건의 가치와 합한 값 14

와 비교 후 최대값을 대입한 값이다.

 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.Math.max;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int N = Integer.valueOf(line.split(" ")[0]);        //물품의 수
        int K = Integer.valueOf(line.split(" ")[1]);        //무게 제한

        int things[][] = new int[N][2];
        for (int i = 0; i < N; i++) {
            line = br.readLine();
            things[i][0] = Integer.valueOf(line.split(" ")[0]);
            things[i][1] = Integer.valueOf(line.split(" ")[1]);
        }

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

        int max = 0;
        for (int i = 1; i < N + 1; i++) {
            max = (max > dp[i][K]) ? max : dp[i][K];
        }

        System.out.println(max);

    }
}