0-1 knapsack 문제정리

0-1 knapsack 문제란 배낭에 담을 수 있는 무게에 서로 무게가 다른 값어치의 물건을 담는다고 할 때 가방에 담을 수 있는 최대 값를 계산하는 방법이다.

knapsack 문제는 Fractional knapsack 과 0-1 knapsack 두개 가 있는데

• Fractional knapsack은 쪼개서 일부 선택 가능한 knapsack 문제이고
• 0-1 knapsack : 아이템을 0개 또는 1개만 선택할 수 있는 경우이다.

---

0-1 knapsack 관련 문제를 푸는 이유

이 중에서 DP에 대한 개념을 더 잘 이해하기 위해 0-1 knapsack을 고르게 되었다.

0-1 knapsack을 그리디로 풀어서는 안되는 이유

가방의 무게가 50일때 물건들이 다음과 같은경

value : 60 , 100 , 120

weight : 10 , 20 , 30

다음과 같이 존재 할때 Greedy로 풀게 될때

각 값의 최대 가치의 비율은 6 , 5, 4 로 첫번째와 두번째 물건을 선택해야 되지만 실재로는 두번째와 세번째를 선택할때 값어치가 제일 높다.

이제 dp 로 풀때는 다음과 같이 푼다.

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

public class Solution {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int T;
    static int N, K;
    // N 물건의 갯수
    // K 는 가방의 최대 무게

    static int[][] DP;
    static int[] W , P;

    public static void main(String[] args) throws IOException {
        
        T = Integer.parseInt(br.readLine());
        
        for (int tc = 1; tc <= T ; tc++) {
            st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            DP = new int[N + 1][K + 1];

            W = new int[N + 1]; // 무게
            P = new int[N + 1]; // 가치

            for (int i = 1; i <= N; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int V = Integer.parseInt(st.nextToken());
                int C = Integer.parseInt(st.nextToken());
                W[i] = V;
                P[i] = C;
            }

            for (int i = 1; i <= N ; i++) {
                for (int j = 1; j <= K; j++) {
                    if(W[i] > j){ // 가방에 넣을 수 없는 상태
                        DP[i][j] = DP[i - 1][j];
                    }else{
                        DP[i][j] = Math.max(DP[i - 1][j - W[i]] + P[i], DP[i - 1][j]);
                    }
                }
            }

            sb.append("#").append(tc).append(" ").append(DP[N][K]).append("\\n");            
        }

        System.out.println(sb);
    }
}

핵심 점화식

 if(W[i] > j){ 
      DP[i][j] = DP[i - 1][j];
  }else{
      DP[i][j] = Math.max(DP[i - 1][j - W[i]] + P[i], DP[i - 1][j]);
  }

DP[i][j] : i 개까지 물건을 선택햇을때 가방무게가 j 일 경우 최대의 값어치

(W[i] > j) : 현재 무게가 이미 배낭 무게보다 크면 그냥 이전 무게를 가지고 오면된다.

Math.max(DP[i - 1][j - W[i]] + P[i], DP[i - 1][j]) DP[i - 1][j]) : 이전 최대값

[i - 1] 이전 물건에서

[j - W[i]] 현재 무게를 뺏을때의 최댓값에서

P[i] 현재 가치를 합한 값 중 최대

1. if (W[i] > j): 현재 물건의 무게(W[i])가 현재 배낭의 용량(j)보다 크기 때문에 이 물건은 넣을 수 없으니, i-1번째 물건까지의 최적값(DP[i-1][j])을 가지고 옴
2. else: 현재 물건을 넣을 수 있는 경우
   • 선택 1: 현재 물건을 넣지 않는 경우DP[i - 1][j] 이전 단계에서 이미 계산된, i-1번째 물건까지로 j 용량을 채울 수 있는 최대 가치
   • 선택 2: 현재 물건을 넣는 경우DP[i - 1][j - W[i]] + P[i] 현재 물건(P[i])을 담고, 남은 무게(j-W[i])를 이전 물건들(i-1)로 채워서 얻는 최대 가치의 합입니다.
   추가설명) : 현재 물건을 담으려면 W[i] 만큼의 공간을 확보해야되기 때문에 →j - W[i] 값을 구하면 이전 물건에서의 최대값 DP[i - 1][j - W[i]] i-1 이전 물건에서의 j - W[i] 현재물건을 담앗다고 가정햇을때의 최대값임