배낭 채우기 (Knapsack)

Knapsack 문제의 정형적 정의

• $S = {item_1, item_2, ..., item_n}$, 물건들의 집합
• $w_i : item_i 의 무게, P_i = item_i의 값$
• W = 배낭이 수용 가능한 총 무게
• 문제 정의
  

Knapsack 문제 유형

0 - 1 Knapsack

• 배낭에 물건을 통째로 담아야 하는 문제
• 물건을 쪼갤 수 없는 경우

0 - 1 Knapsack에 대한 완전 탐색 방법

• 완전 탐색으로 물건들의 집합 S에 대한 모든 부분집합을 구한다
• 부분집합의 총 무게가 W를 초과하는 집합들을 버리고, 나머지 집합에서 총 값이 가장 큰 집합을 선택할 수 있다
• 물건의 개수가 증가하면 시간복잡도가 지수적으로 증가한다
  • 크기가 n인 부분합의 수 $2^n$

0 - 1 Knapsack에 대한 탐욕적 방법

1. 값이 비싼 물건부터 채운다
2. 무게가 가벼운 물건부터 채운다
3. 무게 당(예 : kg당) 값이 높은 순서로 물건을 채운다

Fracional Knapsack

• 물건을 부분적으로 담는 것이 허용되는 문제
• 물건을 쪼갤 수 있는 경우

Fracional Knapsack에 대한 탐욕적 방법

• 무게 당(예 : kg당) 값이 높은 순서로 물건을 채운다

배낭 문제를 DP로 접근해 보자.
먼저 배낭 문제의 부분 문제를 찾아내기 위해 문제의 주어진 조건을 살펴보면

• 물건, 물건의 무게, 물건의 가치, 배낭의 용량, 모두 4가지의 요소가 있다.

이 중에서 물건과 물건의 무게는 부분 문제를 정의하는데 반드시 필요하다.

왜냐하면 배낭이 비어 있는 상태에서 시작하여 물건을 하나씩 배낭에 담는 것과 안 담는 것을 현재 배낭에 들어 있는 물건의 가치의 합에 근거하여 결정해야 하기 때문이다.

또한 물건을 배낭에 담으려고 할 경우에 배낭 용량의 초과 여부를 검사해야 한다.

따라서 배낭 문제의 부분문제를 아래와 같이 정의할 수 있다.

• $W = 배낭의 용량(kg)$
• $(v_i, w_i) = 가치(만원), 무게(kg) 물건$
• K[i, w] = 물건 1 ~ i 까지만 고려하고, (임시) 배낭의 용량이 w일 때의 최대 가치 단, i = 1, 2, …, n이고, w = 1, 2, 3, …, W이다
• K[i, w]를 재귀적으로 정리하면
  

• i번째 물건을 고려 할 때
  

• 배낭 문제의 부분 문제간의 함축적 순서는 다음과 같다
• 즉, 2개의 부분 문제 $K[i-1, w-w_i]$과 $K[i-1, w]$가 미리 계산되어 있어야만 $K[i, w]$를 계산할 수 있다

백준 12865 평범한 배낭

2차원 dp

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_12865_G5_평범한_배낭_2차원_dp {
    static int N, K, W, V;
    static int[] weights;
    static int[] values;
    static int[][] dp;
    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());
        K = Integer.parseInt(st.nextToken());
        weights = new int[N+1];
        values = new int[N+1];
        dp = new int[N+1][K+1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            weights[i] = Integer.parseInt(st.nextToken());
            values[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= K; j++) {
                if (j >= weights[i]) {
                    dp[i][j] = Math.max(dp[i-1][j-weights[i]] + values[i], dp[i-1][j]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        System.out.println(dp[N][K]);
        br.close();
    }
}

1차원 dp

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_12865_G5_평범한_배낭_1차원_dp {
    static int N, K, W, V, answer;
    static int[] weights;
    static int[] values;
    static int[] dp;
    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());
        K = Integer.parseInt(st.nextToken());
        weights = new int[N];
        values = new int[N];
        dp = new int[K+1];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            weights[i] = Integer.parseInt(st.nextToken());
            values[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 0; i < N; i++) {
            for (int j = K; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j - weights[i]] + values[i], dp[j]);
            }
        }

        System.out.println(dp[K]);
        br.close();
    }
}