백준 12865 평범한 배낭 [JAVA]

 

0-1 KnapSack Problem

---

대표적인 DP 문제 알고리즘 중 하나로 알려져 있다.

 

DP 란, 큰 문제를 작은 문제로 나누어서 푸는 방법을 일컫는 말이다.

최적 부분 구조를 가진다는 것은 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다는 것입니다.

---

처음에는 Brute Force 로 접근하였지만 시간 복잡도가 2 ^n 으로  시간 초과가 날것이 분명했다.

DP 문제를 풀기 위해서는 '최적의 원리' (Principle of Optimality) 가 성립하는지를 확인해야 하는데,

최적의 원리는 다음과 같다.

 

"어떤 문제의 입력사례의 최적해가 그 입력사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면.

그 문제는 대하여 최적의 원리가 성립한다"

 

평범한 배낭 문제도 적용해 보자

집합 A 를 n 개의 물건들 중에 최적으로 고른 부분집합이라 가정하자.

 

• 집합 A 가 n 번째 물건을 포함하고 있지 않다면, A은 n 번째 물건을 뺀 나머지 n-1 개의 물건들 중에서 최적으로 고른 부분집합과 같다.
• 집한 A 가 n 번째 물건을 포함하고 있다면, A 에 속한 물건들의 총 가치는 n-1개의 물건들 중에서 최적으로 고른 합에다가 물건 n 의 가치 더한것과 같다, (단 n 번째 물건을 넣었을 떄 배낭이 터지지 않아야 한다.) 

p[i, w] 란 i 개의 물건이 있고 배낭의 무게 한도가 w 일때 최적의 이익을 의미한다.

 

• i 번째 물건이 배낭의 한도보다 무거우면 넣을 수 없으므로 i 번째 물건을 뺀 i-1 개의 물건들을 가지고 전 단계의 최적값을 그대로 가져온다.
• 한도 내일 경우, i 번째 물건을 위해 i번째 물건의 무게를 비웠을 때의 최적값에 i 번째 보석의 가격을 더한 값 or i-1 개의 물건들을 가지고 구한 전 단계의 최적값 중 큰것을 선택한다.

 

p 라는 이차원 리스트를 채워나가면서, 필요한 경우 "앞에서 계산한 결과값을 이용해서 다음 칸의 값을 계산한다.

따라서 배낭문제는 DP 문제인것이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    static int k;
    static int n;
    static int[] W;
    static int[] V;
    static int[][] dp;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]); // 물건 개수
        k = Integer.parseInt(s[1]); // 배낭에 들어갈 수 있는 최대무게
        W = new int[n+1];
        V = new int[n+1];

        dp = new int[n+1][k+1];

        for(int i=1; i<=n; i++){
            s = br.readLine().split(" ");
            W[i] = Integer.parseInt(s[0]);
            V[i] = Integer.parseInt(s[1]);
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=k; j++){
                // i 개의 물건 , j 무게한도
                if(j < W[i]) {
                    // 무게 한도를 초과해서 i 번째 물건을 못 넣는 경우
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = Math.max(V[i] + dp[i-1][j - W[i]], dp[i-1][j]);
                }
            }
        }
        System.out.println(dp[n][k]);

    }

}

 

---

6kg 에 n 개의  item 을 담는 문제는

3Kg 을 담았다는 가정  +   3 kg 배낭의 n-1 물건을 담는 최대값

or  3kg 의 물건을 포함하지 않았다고 가정 + 6kg 배낭의  n -1 개의 물건을 담는 최대값

 

3kg 을 담을 수 있는 배낭은 또한 위와 같은 방식으로  2kg 배낭으로 치환할 수 있다.

 

참고 자료 : https://howudong.tistory.com/106