[백준, DP] 12865 평범한 배낭

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

 

과거 Knapsack 문제, 즉 배낭 문제 유형을 풀었기에 보자마자 DP 문제 중 Knapsack 문제란 걸 알았다.

그러나, 분명 풀었었고 공부했다고 했지만 기억이 나지 않았다. 정확히 말하면 점화식과 어떤 원리로 문제를 풀어야 하는지 기억해내지 못했다.

 

고로, 이번 기회에 Knapsack 까지 공부하고 정리할겸 이 글을 쓴다.

 

배낭 문제

• 조합 최적화의 유명한 문제로, 배낭에 담을 수 있는 무게의 최댓값이 정해져있는 경우, ‘일정 가치’와 ‘무게’가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

이런 배낭 문제는 2가지 타입이 있다.

1. 분할가능 배낭문제(Fractional Knapsack Problem)

• 짐을 쪼개는 것이 가능한 경우
• 이는 그리디 알고리즘으로 구현 가능하다.

2. 0 - 1 배낭문제 (0-1 Knapscak Problem)

• 짐을 쪼갤 수 없다.
• 이런 경우는 DP만 가능하다.

 

0-1 배낭 문제 (0-1 Knapsack Problem)

• 오직 물건을 담거나 빼는 것만으로 최대 가치를 구해야하는 문제다. 

 

DP를 활용한 풀이 방식

- $P[i,w]$ : i개의 물건이 있고 배낭의 무게 한도가 w일 때의, 최적값(가치)

- $w$ : 가방의 무게

- $i$ : 가방

- $v_{i} $ : 가방의 가치

- $w_{i} $ : 가방의 무게

 

 

 

즉, 가방의 갯수와 최대 무게까지의 관계에서 최적의 값을 기록하는 과정이다.

 

(가방의 무게당 최적값을 구한다는 것을 늦게 이해해서 점화식 이해가 어려웠다...)

 

N번째 가방에 대해 고민할 때, N번쨰 가방의 무게 $ w_{N} $ 가 현재 고민하고 있는 무게 $ w $보다 작아서 넣을 수 있다면,

이 가방을 안 넣은 경우(N-1번째 최적값) vs 이 가방을 넣은 경우(i-1, 즉 이전 물건까지 고려했던 최적값 + i번째 가방의 가치)

중 큰 값을 고르면 된다.

 

 

 

12865 문제 코드

package Uplus_Java_BaekJoon.DynamicProgramming.Knapsack;

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

public class bj_12865 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());  // 물품 갯수
        int max_weight = Integer.parseInt(st.nextToken());  // 버틸 수 있는 무게
        int[][] stuffs = new int[N+1][2];
        for(int i=1; i<N+1; i++) {
            st = new StringTokenizer(br.readLine());
            stuffs[i][0] = Integer.parseInt(st.nextToken());   // 물건의 무게
            stuffs[i][1] = Integer.parseInt(st.nextToken());   // 물건의 가치
        }
        
        int[][] dp = new int[N+1][max_weight+1];   // 행 : i번째 물건까지 고려했을 때, 열 : j가 최대 무게였을 때, 값 : 최적의 가치

        for(int i = 1; i < N+1; i++) {
            for(int j = 1; j < max_weight+1; j++) {
                //
                if(stuffs[i][0] > j) {  // i번째 물건의 무게가 j 무게보다 커서 못 넣는 경우
                    dp[i][j] = dp[i-1][j];  // i-1번째 무게 값 그대로 가져오기
                } else {
                    // i번째 물건을 넣을 수 있을떄!!
                    /**
                     * 이제, 기존 i-1번째에서 j 무게까지의 최적값([i-1][j]) VS 지금 물건을 넣었을 때 최적값을 비교하는 거야
                     * i-1번째에서 j 무게까지의 최적값 = dp[i-1][j]
                     *
                     * 지금 물건을 넣었을 떄 최적값 = i번째 물건의 무게를 뻈을 때 최적값 + i번째 가치
                     *                       = dp[i-1][j - i번째 물건의 무게) + i번째 가치
                     *                       = dp[i-1][j - stuffs[i][0]) + stuffs[i][1]
                     */

                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - stuffs[i][0]] + stuffs[i][1]);
                }
            }
        }
        System.out.println(dp[N][max_weight]);

    }
}

 

 

위 방법은 2차원 배열을 활용한 방식이다. 당연히 메모리 사용량은 배로 들 것이기에 찾아보니 1차원 배열로도 푸는 방법이 있어서 참고하였다.

그러나, 왜 정확히 역순으로 해야하는지 온전히 이해하지 못한 것 같아 글 하단에 매우 잘 설명한 블로그 링크를 참조하면 좋을 것 같다.

 

        /**
         * 2차원 배열이 아닌 1차원 배열로 처리하는 방법
         *
         * 1. 점화식은 i-1 번째, 즉 바로 이전 행만 참고한다.
         * 그러면, 1차원 배열로 만든 뒤, i-1 번째 index로 읽는 방법으로 구현 가능
         *
         * 단, 연순으로 진행해야한다. 왜? => 이걸 이해못했어
         *
         *
         */

        int[] one_dp = new int[max_weight+1];   // 행 : i번째 물건까지 고려했을 때, 열 : j가 최대 무게였을 때, 값 : 최적의 가치
        for(int i = 1; i < N+1; i++) {
            for(int j = max_weight; j >= stuffs[i][0]; j--) {   // 무게가 최대 K -> 지금 진행하는 가방의 무게까지만 진행(stuffs[i][0])
                // 지금 진행하는 가방의 무게까지만 진행 => 어차피 넣을 수 없는 무게에는 1차원 배열에 추가되지 않음

                // 물건 넣을 수 있을 때,
                /**
                 * i-1번째의 무게 j까지 고려한 최적값 = one_dp[j-1]
                 *
                 * i번째 물건을 넣었을 떄 최적값 = i번째 물건의 무게를 뻈을 때 최적값 + i번째 가치
                 *                       = dp[j- i번째 물건 무게] + i번째 가치
                 *                       = dp[j - stuffs[i][0]) + stuffs[i][1]
                 */

                one_dp[j] = Math.max(one_dp[j], one_dp[j - stuffs[i][0]] + stuffs[i][1]);
            }
        }


        System.out.println(one_dp[max_weight]);

 

 

결과

제일 밑에가 2차원 배열을 사용했을 때, 제일 위에가 1차원 배열을 사용했을 때이다. 메모리는 약 3배 감소한 것을 확인할 수 있다.

 

참조

https://sskl660.tistory.com/88

[Java]배낭 문제(Knapsack Problem)

 

https://velog.io/@jeongbeom4693/JAVA-Knapsack-Problem%EB%B0%B0%EB%82%AD-%EC%B1%84%EC%9A%B0%EA%B8%B0