[백준 2024/01/23] 12865번 평범한 배낭

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

12865번: 평범한 배낭

 

오늘따라 집중도 안되고..ㅠ~~!! 뭔가 손에 잡히지 않지만...

그래도 책상에 앉아는 있어보려고 노력하는 중이다..ㅎ

 

1. 접근 방법

이번 문제는 읽으면서 작년도 알고리즘 시간에 들었던 0/1 Knapsack 이 떠올랐다.

디자인 방법 중에서는, 1) 전체 경우를 헤아려보는 방법, 2) BFS (넓이 우선 탐색) 3) DFS (깊이 우선 탐색) 이 있다.

 

먼저, 1) 전체 경우를 헤아려보는 방법에 대해서 알아보자.

 

이 방법은 P[i, w] 에서 다음으로 더할 것을 선택할 때, 

[1] P[i-1 ,w] -> item_i를 포함하지 않고 넘어가는 경우

[2] P[i-1, w-w_i] + P_i -> item_i를 포함하고 넘어가는 경우

 

중 둘 중 하나를 선택해서 넘어간다. 이런식으로 recursion 을 만들게 되면

모든 경우를 헤아리게 되고, 그 중 많은 가치를 담은 경우를 Max()를 통해서 출력하도록 한다.

위와 같은 profit과 weight를 가지고 있다고 가정해보자. 그렇다면 아래 표의 각각의 값은 어떤 방식으로 얻게 되는가?

 

P[2,4] 를 예로 들어보자. (item 2번 보는데, 4kg 허용)

1) P[1, 4]  => 0

2) P[그 전 계산 값] + P_i

P[1,w-w_i] + P_i  =>  i 는 2 이므로,

P[1, w-w_2] + P_2  => w_2 = 4 이며, w 도 4 이므로,

P[1, 0] + 40   => 0 + 40

 

즉, 1) 0

2) 40

이며 둘 중 더 큰 값은 2) 이므로 2)번을 선택해서 넘어가게 된다.

 

 

하나만 하면 섭하니까... P[2, 9] 를 구하는 방법에 대해서도 알아보자.

1) P[1,9] = 10

2) P[1, 9 - w_2] + P_2

P[1, 5] + 40

10 + 40 = 50

둘 중 더 큰 값은 2) 이므로, 50 이 P[2, 9] 에 들어가게 된다.

 

이를 코드에 적용시키면 다음과 같다.

알고리즘 골격은 geeksforgeeks에서 가져왔다.

참고로, 아래 코드는 12865번 문제에서 시간 초과가 된다.

땡스튜...Rajat Mishra

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class Main {

    /* A Naive recursive implementation
of 0-1 Knapsack problem */

 static int max(int a, int b) { return (a > b) ? a : b; } // 더 큰 값을 return 해주는 함수.

static int knapSack(int W, List<Integer> wt, List<Integer> val, int n) // KnapSack 함수
  {
            // Base Case
            if (n == 0 || W == 0) // 주어진 경우가 0 이거나 담을 수 있는 weight 이 0 인 경우에는 0을 반환.
                return 0;

            if (wt.get(n - 1) > W) // KnapSack의 수용가능한 무게를 넘어가게 된다면 포함할 수 없으므로, 그 경우는 넘어간다.
                return knapSack(W, wt, val, n - 1);

            else // 위에서 언급한 2 경우 중 최댓값을 return하는 부분
                return max(val.get(n - 1)
                                + knapSack(W - wt.get(n - 1), wt,
                                val, n - 1),
                        knapSack(W, wt, val, n - 1));
        }

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

            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            String line = reader.readLine();
            String[] lines = line.split("\\s+");
            int num = Integer.parseInt(lines[0]);
            int W = Integer.parseInt(lines[1]);
            List<Integer> wt = new ArrayList<>();
            List<Integer> val = new ArrayList<>();

            for(int i =0; i<num; i++){
                String[] w_v = reader.readLine().split("\\s+");
                wt.add(Integer.valueOf(w_v[0]));
                val.add(Integer.valueOf(w_v[1]));
            }

            System.out.println(knapSack(W, wt, val, num));
        }
    }
    /*This code is contributed by Rajat Mishra */

 

이제 다음으로, BFS (넓이 우선 탐색)과 DFS(깊이 우선 탐색) 에 대해서 알아볼 것이다.

두 방법의 차이점은 넓게 먼저 탐색할 것인지, 깊이 있게 먼저 탐색할 것인지 이다.

 

두 방법의 장단점으로, DFS (깊이 우선 탐색)은 해가 깊이 위치하면 효율적이다. 목표 노드가 그래프의 깊은 부분에 위치한 경우 BFS 보다 DFS가 더 효율적일 수 있다. 반대로 해가 없거나 깊이 없는 경우 비효율적이다.

 

정답에 대한 근거가 없다고 할 때에는, 아무래도 BFS가 안정적이다고 할 수 있다.

 

두 경우에 대한 그래프 그리는 방법은 다음과 같다.

 

위 사진에서 언급되어 있지 않지만 W = 100 이다.

 

참고로 p와 w는 무게당 profit이 높은 순으로 정렬되어 있다.

여기서 bound를 구하는 것이 관건이다.

bound = g + h 이다. 여기서 g는 지금까지 얻은 profit을 의미하며, h는 앞으로 얻을 profit을 예상한 것이다.

여기서, h를 예상할 때에는 upper bound를 이용해서 구한다. 루트 노드를 예로 들어서 설명해 보자.

 

우선 루트 노드는 아직 아무것도 넣지 않은 상태이기 때문에, 

profit과 weight의 경우 0이라고 할 수 있다.

이제 bound를 구할 차례이다. g의 경우에도 아직 아무것도 넣지 않았으므로 0,

h를 헤아려 보자.

무게 제한이 우선 100 이다. 그렇다면 맨 앞 두개는 쉽게 넣을 수 있다.

w1 + w2 는 80 이기 때문이다. 이제 20이 남았다. 

다음 것의 무게는 40이기 때문에, 이를 넣게 되면 초과되어 넣을 수 없다.

하지만, bound를 구할 때에는 쪼개서 넣을 수 있다고 가정하고 계산한다. (upper bound)

 

세 번째 것의 무게당 가치는 40/40 = 1 이고, 20kg을 넣을 것이므로 1*20 을 더하게 된다.

 

즉, h는 60 + 60 + 20 = 120 이며, bound 는 120을 가지게 된다.

 

다음 경우는 루트 노드에서 item1을 넣었을 때와 넣지 않았을 때로 나뉘어서 계산하게 된다.

이렇게 item2, 3,,, 쭉쭉 내려간다. 만약 구한 bound가 다른 노드의 profit 보다 적게 되면 그 노드에서의 가지치기는 멈춘다.

해당 노드가 가질 수 있는 최대의 profit이 다른 노드의 실제 profit이 넘어섰기 때문에,

더 이상의 계산은 무의미하다.

 

왜냐하면 현재 가지고 있는 bound가 아래 가지를 쳐서 내려갔을 때 bound보다 높을 것이기 때문이다. 

 

아래 코드는 1) 방법의 개선 코드로, 중복된 계산을 없애고자 한 코드이다. dp[n][w] 라는 2차원 배열을 이용해서 계산된 값을 기억해 두고자 하였다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.io.*;
public class b12865 {

    static int max(int a, int b) { return (a > b) ? a : b; } // 최대값 return 해주는 함수

    static int knapSackRec(int W, List<Integer> wt, List<Integer> val, int n, int[][] dp)
    {

        // Base condition
        if (n == 0 || W == 0) // 만약 n이 0이거자 weight 이 0인 경우 0을 반환.
            return 0;

        if (dp[n][W] != -1)
            return dp[n][W]; // 미리 값이 구해져 있던 경우 즉, -1이 아닌 경우 바로 그 값을 이용

        if (wt.get(n - 1) > W)
            return dp[n][W] = knapSackRec(W, wt, val, n - 1, dp); // 무게가 남은 가방 무게 보다 클 때,

        else
            return dp[n][W] = max((val.get(n - 1) + knapSackRec(W - wt.get(n - 1), wt, val, n - 1, dp)),
                        knapSackRec(W, wt, val, n - 1, dp)); // 1) 2) 중에 더 큰 값을 return 해줌.
        }

    static int knapSack(int W, List<Integer> wt, List<Integer> val, int N)
    {

            // Declare the table dynamically
       int dp[][] = new int[N + 1][W + 1];

           
       for (int i = 0; i < N + 1; i++) // table을 초기에 다 -1로 넣어 놓는다.
            for (int j = 0; j < W + 1; j++)
                dp[i][j] = -1;

        return knapSackRec(W, wt, val, N, dp);//이제 찾고자 하는 값을 KnapSackRec에서 찾으려 한다.
    }

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

            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            String line = reader.readLine();
            String[] lines = line.split("\\s+");
            int num = Integer.parseInt(lines[0]);
            int W = Integer.parseInt(lines[1]);
            List<Integer> wt = new ArrayList<>();
            List<Integer> val = new ArrayList<>();

            for(int i =0; i<num; i++){
                String[] w_v = reader.readLine().split("\\s+");
                wt.add(Integer.valueOf(w_v[0]));
                val.add(Integer.valueOf(w_v[1]));
            }

            System.out.println(knapSack(W, wt, val, num));
        }
    }
    /*This code is contributed by Rajat Mishra */