[알고리즘/JAVA] 동적 계획법(DP) : 배낭 채우기 문제 (0-1 Knapsack)

https://en.wikipedia.org/wiki/Knapsack_problem

동적 계획법

 

최적 부분 구조가 가진 중복된 하위 부분해를 사용해서 복잡한 문제를 풀이하는 방법

주로 [Top-Down + 메모리제이션]혹은 [Bottom-Up + 타뷸레이션]을 사용하는 전략을 사용하며동일한 작은 문제가 여러 번 반복되는 경우가 많은 경우 유용하게 사용된다.

 

• Top-down 방식 DP: 재귀 호출을 사용하여 문제를 작은 부분 문제로 나누고, 각 부분 문제의 해를 계산할 때 해당 결과를 저장하고 재활용한다. 이를 통해 중복 계산을 피하고 연산 시간을 절약할 수 있다.
• Bottom-up 방식 DP : 작은 부분 문제부터 시작하여 상위 문제로 올라가면서 저장해둔 부분 문제의 결과를 사용한다.
  

 

동적 계획법(다이나믹 프로그래밍, DP)에 대한 자세한 설명은 아래의 포스팅을 살펴보자.

https://sjh9708.tistory.com/212

[알고리즘/JAVA] 동적 계획법(DP) : 이론과 활용 [+ 파도반 수열 / 1로 만들기 / 계단 오르기]

 

 

 

 

---

문제 : 평범한 배낭 (백준 12865)

 

 

매우 유명한 문제 중 하나인 0-1 배낭 채우기 문제이다.

배낭 채우기 문제는 주어진 한정된 공간(배낭)에 최대한 가치를 담을 수 있는 아이템의 조합을 찾는 문제이다. 일반적으로 배낭은 특정 무게(weight)까지만 수용할 수 있으며, 각각의 아이템은 무게와 가치(value)를 가지고 있다.

주어진 배낭의 용량 내에서 가치를 최대화하기 위해서는 어떤 아이템을 선택해야 하는지가 핵심적인 문제이다.

 

우선 시간 복잡도를 보고 완전 탐색으로는 절대 풀이할 수 없다는 것을 확인하자. 물건의 수가 최대 100이고, 넣거나, 넣지 않거나의 경우의 수를 따져 보았을 때 2^100가지의 경우의 수가 나오게 된다.

 

그리디로도 어렵다. 가장 무게대비 가치가 높은 것을 우선적으로 담더라도, 항상 최적해를 보장하지 않기 때문이다.
가치를 분할할 수 있는 배낭 문제(Fractional Knapsack)에서는 그리디를 유용하게 쓸 수 있지만 0-1 Knapsack에서는 그렇지 않다.

 

 

<예제 입력의 아이템들의 무게와 가치>

무게	가치
3	6
4	8
5	12
6	13

 

만약 배낭의 최대 무게가 14일때 그리디로 풀이한다면 무게가 5와 6인 아이템을 챙겨서 (가치/무게가 가장 높다) 25의 해를 낼 수 있지만, 실제로는 3, 4, 6인 아이템을 챙기는 것, 즉 27이 최적해이다.

 

따라서 우리는 동적 프로그래밍을 통해서 부분해들 간의 규칙성을 살펴보아야 할 필요가 있다.

 

 

 

---

동적 프로그래밍 : 규칙 파악

 

배낭의 무게	1	2	3	4	5	6	7
가치	0	0	6	8	12	13	14

 

우선 가장 간단하게 다음과 같이 생각해보았다. 우선 배낭의 무게는 어떠한 수라도 지정될 수 있으므로 부분해로 쪼개서 생각해보자. 물론 알 수 있는 것이 아무것도 없다.
하지만 다음 표를 그려보면서 우리는 무의식적으로 아이템을 하나씩 포함하거나 제거하면서 어느 것이 클 지, 즉 Max값에 대한 계산을 했다.

따라서 아이템들의 범위도 부분적으로 쪼개보자.

 

---

 

 

	1	2	3	4	5	6	7
-	0	0	0	0	0	0	0
3(6)	0	0	6	6	6	6	6
4(8)	0	0	6	8	8	8	14
5(12)	0	0	6	8	12	12	14
6(13)	0	0	6	8	12	13	14

 

테이블의 행은 해당 아이템을 포함하여 조합하는 경우를 나타낸다.
즉 2행은 [무게 3] 아이템을 조합해서 만들 수 있는 최대 가치, 3행은 [무게 3, 무게 4] 아이템으로 조합해서 만들 수 있는 최대 가치를 나타낸다. 그리고 맨 아래의 행을 보면 위에서 작성했던 표의 최적해와 일치하는 것을 알 수 있다.

 

그렇다면 각각의 셀에서 그 때의 최적해를 계산하는 알고리즘에 대해서 살펴보자.

우선 해당 열의 새로운 아이템을 조합에 넣었을 경우의 최대 가치 vs 넣지 않았을 경우의 최대 가치 중 최대값이 될 것이다.

 

---

 

예를 들어서 배낭의 무게가 7일 경우의 3행을 살펴보자.

• 무게가 4인 아이템을 포함시킨다고 가정해보자. 그렇다면 나머지 무게 3에 대해서 꽉꽉 채울 수 있는 최대값과, 무게가 4인 아이템의 가치를 합하면 해당 경우의 값인 6 + 8 = 14가 나오게 된다.
• 무게가 4인 아이템을 포함시키지 않는 경우에는, 이전 행의 값인 6을 그대로 사용하게 된다. 

따라서 포함시키지 않는 경우(6) vs 포함시키는 경우(14)이므로, 포함시키는 것이 더 좋은 최적해가 된다.

 

 

이번에는 배낭의 무게가 7일 경우의 5행을 살펴보자.

• 무게가 6인 아이템 포함 : 0 + 13 = 13
• 무게가 6인 아이템 포함 X : 14 = 14

따라서 포함시키지 않는 이전 최적해가 현재 최적해가 된다.

 

 

---

 

즉 조합에 넣지 않았을 경우는 이전 열의 값이 된다.
조합에 새로운 아이템을 넣을 경우는 이전 열에서 현재 담으려는 아이템의 무게를 뺀 배낭 무게의 최적해 + 새로운 아이템의 가치가 된다.

 

따라서 각각의 셀을 f(i, j), i번째 아이템의 무게를 w(i)라고 한다면 다음과 같은 식이 성립한다

 

max(f(i-1, j), f(i-1, j - w(i)) + value(w(i)))

 

i번째 아이템을 포함시키지 않는 경우 : f(i-1, j)

i번째 아이템을 포함시키는 경우 :  f(i-1, j - w(i)) + value(w(i))

 

 

---

코드 작성 : Bottom Up 방식

 

public class Main {
    static int n;
    static int[] weight;
    static int[] value;
    static int maxWeight;

    static Integer[][] dp;


    //Bottom Up
    static int knapsack_bu(){
        for(int w = 0; w <= maxWeight; w++){
            dp[0][w] = 0;
        }

        for(int i = 1; i <= n; i++){
            for(int w = 0; w <= maxWeight; w++){
                if(weight[i] > w){
                    dp[i][w] = dp[i-1][w];
                }
                else{
                    dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]);
                }
            }
        }
        return dp[n][maxWeight];
    }



    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());
        maxWeight = Integer.parseInt(st.nextToken());

        weight = new int[n+1];
        value = new int[n+1];
        dp = new Integer[n+1][maxWeight + 1];
        for(int i = 1; i <= n; i++){
            st = new StringTokenizer(br.readLine());
            weight[i] = Integer.parseInt(st.nextToken());
            value[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(knapsack_bu());


    }
}

• weight에는 각 아이템의 무게, value에는 각 아이템의 가치가 들어가게 된다.
• 위에서 파악했던 규칙을 기반으로 동적 프로그래밍을 하기 위한 dp[][] 배열을 선언한다.
• 배열을 채울 때, 2행부터 시작한다. 그리고 1행은 0으로 채워준다. (이전 행을 계산하는 연산이 있기 때문에 NullException 방지)
• 해당 아이템 1개의 무게가, 배낭의 무게를 초과하지 않는 경우에는 포함하는 경우와 포함하지 않는 경우의 최적해를 비교한다.
  • dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
• 반대로 해당 아이템 1개의 무게가, 배낭의 무게를 초과하는 경우에는 비교할 필요도 없이 포함하지 않는 경우의 최적해가 현재 최적해가 된다. (애초에 배낭의 무게를 초과하면 어떻게 해도 넣지 못함)
  • dp[i][w] = dp[i-1][w]
• 최종적으로 동적 프로그래밍으로 얻어낸, 가방이 입력값으로 주어진 무게(최대 무게)일 경우의 최적해를 반환하자.

 

 

---

코드 작성 : Top-down 방식

 

public class Main {
    static int n;
    static int[] weight;
    static int[] value;
    static int maxWeight;

    static Integer[][] dp;


    // Top Down
    static int knapsack_td(int i, int w){
        if(i < 0){
            return 0;
        }
        if(dp[i][w] == null){
            if(weight[i] > w){
                dp[i][w] = knapsack_td(i - 1, w);
            }
            else{
                dp[i][w] = Math.max(knapsack_td(i - 1, w), knapsack_td(i - 1, w - weight[i]) + value[i]);
            }
        }
        return dp[i][w];
    }


    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());
        maxWeight = Integer.parseInt(st.nextToken());

        weight = new int[n+1];
        value = new int[n+1];
        dp = new Integer[n+1][maxWeight + 1];
        for(int i = 1; i <= n; i++){
            st = new StringTokenizer(br.readLine());
            weight[i] = Integer.parseInt(st.nextToken());
            value[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(knapsack_td(n, maxWeight));


    }
}

 

• Bottom-up + 타뷸레이션 방식을 Top-down + 메모리제이션 방식으로 변환한 것 외에 기본적인 동작 방식은 동일하다.