[백준] 12865. 평범한 배낭 (DP) - JAVA

문제

 

---

 

풀이

 

해당 문제는 가장 유명한 배낭 문제이다.

 

동적 프로그래밍(DP)를 활용해서 풀어야 한다.

우선, 시간 복잡도는 (N*M) 이다.

 

문제에서 받은 데이터인

물품 개수 N  = 4

가방의 무게 K = 7 로 풀이를 해보겠다.

 

2중 for문을 통해서 DP[ ][ ] 값을 채워넣을 건데

먼저 비교식부터 알려주자면,

i = 가방의 넣을 수 있는 물품 위치

w = 현재 무게

 

DP[ i ][ w ] = Math.max(DP[ i-1 ][ w ] , DP[ i-1 ][ w-(i의무게) ] + i의 가치)이다.

쉽게 말하자면, 

현재 물품을 추가하지 않고 그대로 가기

vs

현재 물품만큼 가방을 비우고, 현재 물품 추가하기

 

아래에서 표를 통해 확인해보자.

 

	[0]	[1] (6,13)	[2] (4,8)	[3] (3,6)	[4] (5,12)
0 kg	0	0	0	0	0
1 kg	0
2 kg	0
3 kg	0
4 kg	0
5 kg	0
6 kg	0
7 kg	0

우선, 물품이 0개인 경우 당연히 최대값은 0kg이다.

 

	[0]	[1] (6,13)	[2] (4,8)	[3] (3,6)	[4] (5,12)
0 kg	0	0	0	0	0
1 kg	0	0
2 kg	0	0
3 kg	0	0
4 kg	0	0
5 kg	0	0
6 kg	0	13
7 kg	0	13

다음으로는 물품[1] 이 들어갈 수 있는 경우이다.

물품[1]의 크기는 6kg이므로, 가방의 무게가 6kg이상일 때 들어갈 수 있다.

 

	[0]	[1] (6,13)	[2] (4,8)	[3] (3,6)	[4] (5,12)
0 kg	0	0	0	0	0
1 kg	0	0	0
2 kg	0	0	0
3 kg	0	0	0
4 kg	0	0	8
5 kg	0	0	8
6 kg	0	13	13
7 kg	0	13	13

다음으로는 물품[1]과 물품[2]가 들어갈 수 있는 경우이다.

가방의 무게가 4kg와 5kg 인 경우는 물품[2]가 들어갈 수 있지만,

가방의 무게가 6kg, 7kg 인 경우는 물품[1]만 들어가는게 더 높은 최대치이다.

비교는 위에서 말했던 식으로 비교 가능하다.

DP[ 2 ][ 6 ] = Math.max( DP[ 2-1 ][ 6 ] , DP[ 2-1 ][ 6 - 4 ] + 8 )

DP[ 1 ][ 6 ] = 13

DP [ 1 ] [ 2 ] + 8 = 8

즉 , 13이 더 높기 때문에 새로운 물품을 추가하지 않고,

그대로 이전에 있던 물품을 가져가는 것이다.

 

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

이제 물품[3]도 고려하여 추가해보자.

그리고 7kg인 경우는 14 로 가장 최대값이 되었다. 식을 통해 확인해보자.

DP[ 3 ][ 7 ] = Math.max( DP[ 3-1 ][ 7 ] , DP[ 3-1 ][ 7 - 3 ] + 6 )

DP [ 2 ][ 7 ] = 13

DP[ 2 ][ 4 ] + 6 = 14

따라서 7kg인 경우에는 14이다.

 

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

마지막으로 물품[4]까지 고려하여 채워넣고,

DP[ 4 ][ 7 ] = 14 로

이 배낭문제에서 최대값은 14로 확인 할 수 있다.

 

---

 

코드

 

import java.io.*;

import java.util.*;

 

public class Main{

    static int N, K;

    static int[][] DP;

    static int[][] bags;

 

    static void find(){

        for(int i=1; i<=N; i++){

            for(int w=1; w<=K; w++){

                DP[i][w] = DP[i-1][w];

                if( w>=bags[i][0]){

                    DP[i][w] = Math.max(DP[i][w] , DP[i-1][w-bags[i][0]]+bags[i][1]);

                }

            }

        }

    }

 

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        K = Integer.parseInt(st.nextToken());

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

        bags = new int[N+1][2];

        for(int i=1; i<=N; i++){

            st = new StringTokenizer(br.readLine());

            bags[i][0] = Integer.parseInt(st.nextToken());

            bags[i][1] = Integer.parseInt(st.nextToken());

        }

        find();

        System.out.print(DP[N][K]);

    }

}