냅색(Knapsack) 알고리즘

📌 냅색(Knapsack) 문제란

 

어떤 가치를 가진 물건이 여러 개 있을 때, 특정 조건을 만족하는 조합을 구하는 문제로 작은 문제의 결과로 큰 문제의 결과를 해결하는 다이나믹 프로그래밍의 대표적인 문제

 

여기서는 물건의 가치를 쪼갤 수 없는 0-1 Knapsack 문제를 설명한다.

 

📌 점화식

 

다이나믹 문제를 해결하기 위해서는 먼저 점화식을 세워야 한다.

 

아래 그림을 보자

 

문제 예시

 

빈 상자에 20kg을 담을 수 있다. 해당 무게만큼 담을 때, 담은 공의 가격이 가장 높은 케이스를 찾는 것이다. 즉, 특정 조건 내에서 가장 가치합이 높은 조합을 찾는 것이다.

 

🔎 타뷸레이션 & 메모이제이션

 

• 타뷸레이션 : 작은 문제의 정답을 이용하여 큰 문제를 해결하는 방법
• 메모이제이션 : 이미 계산된 값을 다시 계산해야 할 때, 이미 계산된 값을 재활용하는 방법

 

위와 같은 방법으로 다이나믹 문제를 풀이한다. 이를 응용하면 아래와 같아진다.

 

상자에 10$ 5kg 공을 넣음

 

만약 10$, 5kg 공을 넣었을 때 20kg 무게 이하를 만족하는 최대 가치는 무엇과 동일할까

 

남은 공과 상자 상태

 

그것은 20kg에서 5kg을 뺀 15kg 상자에 남은 공을 넣어서 만드는 최대 가치합과 동일한 의미다.

 

🔎 식으로 접근

 

그래서 다음과 같이 정의할 수 있다.

 

dp[i][j]: i번 물건까지 진행했고 j 무게일 때 최대 가치합

 

최종적으로 구해야 하는 값: dp[물건 개수][최대 무게]

 

0-1 Knapsack 문제는 해당 물건을 포함하거나 하지 않는 경우로 나누어 최대 가치를 계산하는 것이다.

 

그런데 모든 무게마다 최대 가치합을 구해야 하기 때문에 무게를 초과하는 경우와 그렇지 않은 경우로 나눠야 한다.

 

✔ 무게를 초과하는 경우

 

무게를 초과할 경우 현재 물건을 포함할 수 없다.

 

dp[i][j] = dp[i - 1][j]      //dp[i - 1][j]는 앞 물건에서 구한 최대 가치합

 

✔ 무게를 초과하지 않은 경우

 

이 때는 두 가지 경우로 나눌 수 있다. 먼저, 현재 물건을 포함하지 않을 수 있다. 또 하나는 현재 물건을 포함하는 것이다. 둘 중 더 큰 가치합을 선택하면 된다.

 

dp[i][j] = max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]])         //v[i] : 현재 물건의 가치, w[i] : 현재 물건의 무게

 

• dp[i - 1][j]는 현재 물건을 포함하지 않은 경우
• v[i] + dp[i - 1][j - w[i]]는 앞서 살펴본 그림과 동일하다.
  • 앞 물건까지 최대 가치합 => dp[i - 1][j], 무게에 따라서 이전 물건까지 포함하거나 포함하지 않은 최대 가치합
  • v[i] + dp[i - 1][j - w[i]] => 현재 물건을 포함했을 때 최대 가치합
• 즉, 이전 물건을 (포함o 또는 포함x) 2가지 경우 + 현재 물건을 포함o 또는 포함x

 

최대 가치합 조합

 

🔎 모든 경우의 최대 가치합

 

/무게 개수	0	1	2	3	4	5	6	7	8	9	10
0	0	0	0	0	0	0	0	0	0	0	0
1(10,5)	0	0	0	0	0	10	10	10	10	10	10
2(25,12)	0	0	0	0	0	10	10	10	10	10	10
3(15,8)	0	0	0	0	0	10	10	10	15	15	15
4(6,3)	0	0	0	6	6	10	10	10	16	16	16
5(7,4)	0	0	0	6	7	10	10	13	16	17	17

 

• 개수가 0일 때는 넣은 물건이 없으므로 모두 0이다.
• 개수가 1개일 때는 해당 물건을 넣지 않거나(0) 넣을 수 있는 무게부터는 넣는 경우(10) 둘 중 하나다.

 

/무게 개수	11	12	13	14	15	16	17	18	19	20
0	0	0	0	0	0	0	0	0	0	0
1(10,5)	10	10	10	10	10	10	10	10	10	10
2(25,12)	10	25	25	25	25	25	35	35	35	35
3(15,8)	15	25	25	25	25	25	35	35	35	40
4(6,3)	21	25	25	25	31	31	35	35	35	41
5(7,4)	21	25	25	25	31	32	35	35	38	41

 

• ex) dp[3][20] = max(dp[2][20], 15 + dp[2][20 - 8])
  • dp[2][20] = 1번과 2번 물건 선택
  • dp[2][12] = 2번 물건 선택
  • dp[3][20] = 큰 값 {(1번 + 2번 선택), (2번 + 3번 선택)}

 

이런 식으로 테이블을 채워나가게 된다.

 

📌 구현(2차원 배열)

 

import java.io.IOException;

public class Main {

    public static void main(String[] args) throws IOException {
        int N = readInt(); //물건 개수
        int M = readInt(); //제한 무게
        Case[] A = new Case[N + 1]; //각 물건 정보
        int[][] dp = new int[N + 1][M + 1]; //i 번째 케이스까지 남은 무게가 j였을 때 최대 가치합

        for (int i = 1; i <= N; i++) A[i] = new Case(readInt(), readInt());

        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= M; j++) { //제한 무게
                if (A[i].w > j) dp[i][j] = dp[i - 1][j]; //무게 초과
                else dp[i][j] = Math.max(dp[i - 1][j], A[i].v + dp[i - 1][j - A[i].w]); //max(포함x, 포함o)
            }
        }

        System.out.println(dp[N][M]);
    }

    static class Case {
        int v; //가치
        int w; //무게

        public Case(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    static int readInt() throws IOException {
        int c, n = System.in.read() & 15;
        while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

}

 

📌 구현(1차원 배열)

 

위 테이블을 1차원 배열로 표현할 수 있다. 그 이유는 이전에 저장된 dp 값만 참고하면 되므로 새로운 값으로 덮어쓰면 되기 때문이다.

 

💡 주의

모든 물건은 단 한 번씩만 계산되어야 한다. 그런데, 무게 오름차순으로 최대 가치합을 계산할 경우 물건을 중복해서 계산하는 경우가 발생한다.

ex) 위 테이블 참고
첫 번째 물건(10,5) 를 계산할 때 => dp[10] = dp[5] + 10 (20)    //dp[5] 는 10이므로 dp[10]은 (10,5) 물건을 2번 계산한 것

따라서 무게 내림차순으로 최대 가치합을 계산해야 중복을 방지할 수 있다.

 

import java.io.IOException;

public class Main {

    public static void main(String[] args) throws IOException {
        int N = readInt(); //물건 개수
        int M = readInt(); //제한 무게
        Case[] A = new Case[N + 1]; //각 물건 정보
        int[] dp = new int[M + 1]; //남은 무게가 i였을 때 최대 가치합

        for (int i = 1; i <= N; i++) A[i] = new Case(readInt(), readInt());

        for (int i = 1; i <= N; i++) {
            for (int j = M; j > 0; j--) { //중복 포함 방지
                if (A[i].w <= j) dp[j] = Math.max(dp[j], A[i].v + dp[j - A[i].w]); //max(포함x, 포함o)
            }
        }

        System.out.println(dp[M]);
    }

    static class Case {
        int v; //가치
        int w; //무게

        public Case(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    static int readInt() throws IOException {
        int c, n = System.in.read() & 15;
        while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

}

 

References:

 

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의

 

https://howudong.tistory.com/106

배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기

 

https://chanhuiseok.github.io/posts/improve-6/

[알고리즘 트레이닝] 5장 - 동적계획법과 냅색(Knapsack) (백준 12865번 평범한 배낭 문제로 살펴보기)