[PS] BOJ12865 평범한 배낭 ( DP ) with JAVA

12865번: 평범한 배낭

 

 

◎ 문제풀이 

 

무게 제한이 있는 배낭에 아이템을 넣는 경우, 가치의 최댓값을 구하는 문제이다. 

 

2가지 경우를 생각할 수 있다.

 

1) 배낭에 넣는 경우

2) 배낭에 넣지 않은 경우

 

그래서 DFS로 2가지 경우를 완전 탐색해도 될거 같지만, DP로 문제를 풀어보겠다. 

무게 제한이 7인 배낭에 아이템1( 무게 6 ), 아이템2( 무게 4) , 아이템3( 무게 3 ), 아이템4( 무게 5 )를 넣으려고 한다. 

 

 

 

 

 

아이템1에서 아이템4까지  넣는 경우와 넣지 않은 경우를 처리하며 dp에 메모리제이션을 한다. 4번째 아이템에 왔을 때는, 4가지 아이템의 경우를 모두 고려한 dp 계산이 가능해진다. 

 

 

◎ 코드

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

//BOJ12865 평범한 배낭
public class Main {

    public static class Item{

        int weight;
        int value;

        public Item(int weight, int value){
            this.weight = weight;
            this.value = value;
        }
    }

    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());

        Item[] items = new Item[n+1];

        for(int i=1;i<=n;i++){
            st = new StringTokenizer(br.readLine());

            int weight = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            items[i] = new Item(weight,value);
        }

        int[][] dp = new int[n+1][k+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=k;j++){
                dp[i][j] = dp[i-1][j];

                if(j-items[i].weight < 0) continue;
                dp[i][j] = Math.max(dp[i][j], dp[i-1][j-items[i].weight] + items[i].value );
            }
        }

        System.out.println(dp[n][k]);

    }
}