[백준] 12865: 평범한 배낭 (1/0 Knapsack problem, DP) - JAVA

class 4

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

 

 

 

 

# 문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

 

 

# 예제

입력 : 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

4 7
6 13
4 8
3 6
5 12

 

출력 :  한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

14

 

 

# 필요개념

정해진 무게에 맞게 물건을 담아 최대 가치를 끌어내는 문제로, 0/1 Knapsack problem 이라는 이름으로 배웠던 기억이 있다. 해당 물건을 넣을지 말지를 결정해야하기 때문에, dp로 문제를 푸는 것이 적절하다.

 

나는 이차원배열을 이용해 문제를 풀었다. 어짜피 지정된 무게 이하로 물건을 넣어야 하기 때문에, (N + 1) * (K + 1) 사이즈의 배열을 만들고 해당 무게를 만족하는 가장 큰 value를 배열에 넣는 방식으로 풀기로 했다.

 

위 예제를 예시로 설명하면 아래와 같다.

우선  (N + 1) * (K + 1) 사이즈의 dp배열을 생성한다. +1을 해서 생성하는 이유는, 풀이 과정에서 i - 1등 이전 칸의 값을 이용할 것이기 때문이다.

 

참고로 현재상황은 j = 1~K 까지의 값을 보여줄 것이다.

• 첫번째 물건은 weight: 6, value: 13이다.
  • dp[1][6] = 13을 대입하게 된다. 나머지 칸은 값이 0으로 채워진다.
  • 현재상황 : 0 0 0 0 0 13 0
• 두번째 물건은 weight: 4, value: 8이다. 
  • dp[2][4] = 8로 채워진다.
  • 여전히 무게가 6인 경우 최대값은 이전에 채운 dp[1][6]과 동일하므로 dp[2][6] = 13 을 대입한다.
  • 첫 물건과 두번째 물건을 모두 넣고싶을 수 있으므로, 우선 무게를 체크한다 -> 4 + 6 > K 이므로 넣지 않는다. 
  • 현재 상황 
    • 0 0 0 0 0 13 0
    • 0 0 0 8 0 13 0
• 세번쨰 물건은 weight: 3, value: 6이다.
  • dp[3][3]은 6으로 채워진다.
  • 이전줄에서 4번째 값과 6번째 값이 있으므로 각각 현재 줄에도 넣어준다.
  • 두번째 물건의 무게가 4였고, 현재는 3이므로 4 + 3 < K를 만족한다. 그러므로 dp[3][7] = 8 + 6 = 14를 넣어준다.
  • 첫번째 물건의 무게는 6이고 현재 무게는 3이므로 6 + 3 > K로 값을 넣지 않는다.
  • 현재상황
    • 0 0 0 0 0 13 0
    • 0 0 0 8 0 13 0
    • 0 0 6 8 0 13 14
• 네번째 물건은 weight: 5, value: 12이다.
  • dp[4][5] = 12로 채워진다.
  • 이전 줄에 들어가있던 값들을 현재 줄에 넣어준다.
  • 이전 물건들 중 무게가 2 이하는 경우가 없으므로 새로운 값이 들어가지 않는다.
  • 최종상황
    • 0 0 0 0 0 13 0
    • 0 0 0 8 0 13 0
    • 0 0 6 8 0 13 14
    • 0 0 6 8 12 13 14

 

이렇게 넣으면 마지막줄의 최대값인 14가 답이 된다.

 

# Code

import java.io.*;
import java.util.*;
import static java.lang.Math.*;
public class Main {
    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[][] weightValue = new int[N + 1][2];
        int[][] dp = new int[N + 1][K + 1];
        for (int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine());
            weightValue[i][0] = Integer.parseInt(st.nextToken()); // weight
            weightValue[i][1] = Integer.parseInt(st.nextToken()); // value
        }

        for (int i = 1 ; i <= N ; i++) {
            int w = weightValue[i][0];
            int v = weightValue[i][1];
            for (int j = 1 ; j <= K ; j++) {
                if (dp[i - 1][j] != 0) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j]);
                }
                if (w > K) continue;
                if (dp[i - 1][j] != 0 && j + w <= K) {
                    dp[i][j + w] = max(dp[i - 1][j + w], dp[i - 1][j] + v);
                }
            }
            if (w > K) continue;
            dp[i][w] = max(dp[i][w], v);
        }
        int max = 0;
        for (int i = 1 ; i <= K ; i++) {
            if (max < dp[N][i]) max = dp[N][i];
        }
        System.out.println(max);
    }
}

 

 

# 결과