[SWEA/D3/DP/자바] 0/1 Knapsack

💡 문제

 

민수에게는 1번부터 N번까지의 번호가 부여된 N(1≤N≤100)개의 물건과 최대 K(1≤K≤1000)

부피만큼을 넣을 수 있는 가방이 있다.
1번 물건부터 N번 물건 각각은 부피  Vi와 가치 Ci 를 가지고 있다. (1≤Vi, Ci≤100)
민수는 물건들 중 몇 개를 선택하여 가방에 넣어서 그 가치의 합을 최대화하려고 한다.
단, 선택한 물건들의 부피 합이 K 이하여야 한다.
민수가 가방에 담을 수 있는 최대 가치를 계산하자

 

⌨ 입력 

 

첫째 줄 : 테스트 케이스 수(T)

각 테스트 별 : 물건의 수(N) 가방의 부피(K) 주어진다.

이후 N개의 줄 : 부피(Vi), 가치(Ci)

 

💻 출력 / 제한

 

각 테스트 케이스 마다 담을 수 있는 최대 가치를 출력한다. (케이스당 0.2초)

 

---

 

풀이 방법 

 

napsack 문제는 두 가지로 풀 수 있다.

1. DFS를 통한 이진트리 ( 해당 물건을 포함 하는가, 안하는가 )
2. DP를 통한 최대값 갱신

 

DFS 시간 복잡도 :

 

2의 n승이 나온다. (n = 물건의 개수)

물건이 최대 100개 이므로 2의 100승 = 1024의 10승 이므로 불가능 하다.

 

DP 시간 복잡도 :

2중 for문으로 물건의 개수 * 최대 부피 이다.

물건의 개수 100 * 최대 부피 1000 이므로 십만 이므로 가능 하다.

 

 

배열 정보

열 : 현재 부피
열 표시된 값 : 물건의 가치
행 :  i번째 물건

 

 

포함 불가능 :

i번째 물건의 부피가 size[i] 일때,
현재 부피(j) 보다 클 경우에는 물건을 포함 할 수 없다.

dp[i][j] = dp[i-1][j];

포함 가능:

dp[i-1][j] : 물건을 포함 하지 않은 경우
dp[i-1][ j - size[i]] + price[i] : 물건을 포함 하려면 현재 부피에서 물건의 부피를 빼야한다.

두 값(가치) 중 큰 값을 넣는다.

 

 

전체 코드

 

public class Knapsack {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());

        for(int t = 1; t <= testCase; t++) {
            int[] NandK = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int N = NandK[0];
            int K = NandK[1];

            int[] size = new int[N + 1];
            int[] price = new int[N + 1];

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

            for(int i = 1; i <= N; i++) {
                int[] sizeAndPrice = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                size[i] = sizeAndPrice[0];
                price[i] = sizeAndPrice[1];
                dp[i][size[i]] = price[i];
            }

            for (int i = 1; i < dp.length; i++) {
                for(int j = 1; j < dp[0].length; j++) {
                    if(j < size[i]) {
                        dp[i][j] = dp[i-1][j];
                    }
                    else {
                        dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - size[i]] + price[i]);
                    }
                }
            }
            String st = "#" + t + " " + dp[N][K];
            System.out.println(st);
        }
    }
}