Knapsack 유형

• 0-1 Knapsack
  • 쪼갤 수 없는 물건을 배낭에 담는 문제
  • Dynamic programming 문제
• Fractional Knapsack
  • 쪼갤 수 있는 물건을 배낭에 담는 문제
  • Greedy 문제

📌 0-1 Knapsack

• 쪼갤 수 없는 가중치를 담을 때 사용하는 알고리즘이다.
• 탐욕적 방법으로 최적해를 찾을 수 없다.
• 동적 계획법을 사용하여 풀 수 있다.

문제 예시

Q1.각 물건이 하나만 있는 경우 담을 수 있는 최대가치?

Q. 10kg의 용량의 배낭에 다음과 같은 4가지의 물건을 넣을 수 있을 때, 최대의 가치가 되도록 배낭을 채우려면?

• 5kg/10만원, 4kg/60만원, 3kg/10만원, 6kg/40만원

💡 생각할 포인트! - 상향식 DP, 가방안에 부분 가방!!
물건 i에 대해 가방의 무게를 w로 했을 경우

• 물건 i가 가방 무게 w를 초과인 경우 (담지 못한다)
• 물건 i가 가방 무게 w이하인 경우 (담을 수 있다)
  -> 현재 물건을 고려했을 때의 최대 가치 = Max(현재 고려하는 물건을 담는다, 현재 고려하는 물건을 담지 않는다)

DP 배열 정의

dp[i][w] : 물건1번부터 i까지를 고려하여 가방 무게 w이하를 만족 시킬 때의 최대 가치

• dp[i]가 필요한 이유 : 각 물건이 하나만 있기 때문에 현재 물건 i를 선택하면 물건 i를 선택하지 않은 i-1까지에서만 최대 value를 구해야한다.
  만약 물건을 중복하여 선택해도 된다면, 현재 물건을 선택함에 따라 이전 물건까지만 고려하는 것을 안해도 된다. -> Unbounded Knapsack Problem

점화식

K : dp배열, V: 가치, W : 부분 배낭의 무게, i:현재 고려해야 할 물건

• 물건 i가 가방 무게 w이하인 경우 (담을 수 있다)
  k[i][w] = MAX(Vi + k[i-1][W-wi], k[i-1][w])
• 물건 i가 가방 무게 w를 초과인 경우 (담지 못한다) - 직전 값 저장
  k[i-1][w]

/*
* dp[i][w] = 배낭 w일때, 물건 i까지의 최대 가치
*
* dp[i][w] =
* 물건 i를 담지 않는다 -> 이전(i-1) 물건을 담는 것 까지의 최대 가치 = dp[i-1][w];
* 물건 i를 담는다 -> 현재 물건(i)의 가치 + 가방 무게(w)에서 현재 물건(i)의 무게를 뺀 최대 가치 중 더 큰 가치 = Max(dp[i-1][w], value[i] + dp[i-1][w - iw])
*
* */


        int n = Integer.parseInt(st.nextToken()); // 물품 수
        int W = Integer.parseInt(st.nextToken()); // 가방 무게

        int[][] goods = new int[n+1][2];

        for(int i=1;i<=n;i++){
            st = new StringTokenizer(br.readLine());
            int iw = Integer.parseInt(st.nextToken()); // 물건 무게
            int iv = Integer.parseInt(st.nextToken()); // 물건 가치
            goods[i][0] = iw;
            goods[i][1] = iv;
        }
        int[][] dp = new int[n+1][W+1];

        for(int i=1;i<=n;i++){  // 물건
            for(int j=1;j<=W;j++) {  // 임시 가방
                int iw = goods[i][0]; // 물건 무게
                int iv = goods[i][1]; // 물건 가치
                if (iw > j) { // 물건 무게가 임시 가방 보다 클 때,
                    dp[i][j] = dp[i-1][j]; // 이전 물건까지의 최대 가치
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], iv + dp[i-1][j-iw]);
                }
            }
        }
        System.out.println(dp[n][W]);

공간 복잡도 개선

방법1. 2차원 배열의 2행까지만 사용하기

• 직전의 최적해만 필요하기 때문에 2개의 행만을 번갈아 사용하여 공간복잡도를 개선할 수 있다.

방법2. 역순으로 고려하여 일차원 배열 하나만 사용하기

• 현재 고려해야 할 가방의 무게보다 큰 무게는 고려할 필요가 없기 때문에 역순으로 최적해를 구하면 앞으로 구해야 할 최적해에 영향을 미치지 않아 일차원 배열로 구할 수 있다.

        int[] dp = new int[W+1];

        for(int i=1;i<=n;i++){  // 물건
            for(int j=W;j>=1;j--) {  // 임시 가방 (역순으로 하여 물건을 중복으로 선택하는 것을 제거)
                int iw = goods[i][0]; // 물건 무게
                int iv = goods[i][1]; // 물건 가치
                if (iw <= j) {
                    dp[j] = Math.max(dp[j], iv + dp[j-iw]);
                }
            }
        }
        System.out.println(dp[W]);