[알고리즘] 배낭 문제(Knapsack Problem)

Concept

• 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제

Feature

배낭 문제에는 두 가지 유형이 존재

• Fractional Knapsack : 물건을 쪼갤 수 있음. 무게나 가치가 소수점 단위로 나뉠 수 있는 문제.
• 0-1 Knapsack : 물건을 쪼갤 수 없음. 무게나 가치가 무조건 정수타입을 가지는 문제.

Implement

Brute-Force

• 가장 기본적인 풀이방법으로써 N개의 물건에 대해 가능할 수 있는 모든 조합을 만들어 보는 접근법. 시간복잡도는 O(2^N)으로 많이 느리다고 볼 수 있다.

Dynamic Programming

• DP의 핵심은 메모이제이션으로 문제(가방에 넣을 수 있는 최대 가치)를 해결하는 과정에서 이루어지는 부분문제(i번째 물건에 대해서 배낭에 넣을 것인지 넣지 않을것인지)의 해를 dp배열에 저장하고 재사용하는 것.

0-1 Knapsack

• 위의 부분문제를 해결하기 위해 고려해야 할 것은 각각의 물건들에 대해
  • 넣는다.
  • 넣지 않는다.
• 위 두 가지를 고려해야함.
• 우선 문제를 해결하기 전 메모이제이션을 할 dp배열을 초기화해야 하는데
  • 행(각각의 물건), 행의 크기(물건의 개수)
  • 열(무게), 열의 크기(담을 수 있는 최대 무게)
• 위와같이 배열을 선언하고, 뒤에 수행할 풀이로는 각각의 무게별로 현재 행의 물건을 담을 수 있는지에 대해 찾는 것으로 진행.
• 아래는 0-1 Knapsack과 관련하여 백준의 기초적인 문제 풀이

BOJ_12865 평범한 배낭

BOJ_12865 평범한 배낭

 

Source Code

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

//BOJ_12865 평범한 배낭
public class Main {
    static int N, K;
    static int[][] dp, item;

    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());

        item = new int[N+1][2]; //물건의 무게와 가치를 담을 배열
        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            item[i][0] = Integer.parseInt(st.nextToken()); //무게
            item[i][1] = Integer.parseInt(st.nextToken()); //가치
        }

        dp = new int[N+1][K+1];

        for(int i=1; i<=N; i++) { //i는 물건의 번호라 생각
            for(int j=1; j<=K; j++) { //j는 1부터 최대무게 K까지
                if(item[i][0] <= j) { //현재 물건을 담을 수 있다면
                    //이전 가치보다 현재 물건을 담았을때의 가치가 높을 경우
                    if(item[i][1] + dp[i-1][j-item[i][0]] > dp[i-1][j]) {
                        dp[i][j] = item[i][1] + dp[i-1][j-item[i][0]]; //이전 가치에서 이전 물건의 무게만큼 뺀 dp배열을 참조.
                    }
                    else dp[i][j] = dp[i-1][j]; //이전 가치 그대로 사용
                }
                else { //담을 수 없을 경우 이전 가치를 그대로 사용
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        System.out.println(dp[N][K]); //최대가치 출력
    }
}

풀이 과정
1. dp배열 초기화
2. 각 물건마다 1~K까지의 무게 별로 로직 수행
3. i물건의 무게보다 j가 크다면 == 즉 i물건을 배낭에 담을 수 있다면 두가지 case 고려
3-1. 이전 물건을 담았을 때 보다 현재 물건을 담았을 때가 가치가 더 클 경우 값 갱신
3-2. 이전 물건을 담았을 때가 가치가 더 클 경우 dp 부분문제 해 재사용
4. i물건의 무게보다 j가 작다면 == i물건을 배낭에 담을 수 없을 때는 부분문제 해 재사용

• 3-1 부분에서 dp[i][j]에 값을 갱신하는게 조금 이해가 안될 수 있으니 조금 더 자세하게 설명을 해보자면
• 아래와 같은 입력에 대해서

4 7 (물건 개수, 배낭의 최대 무게)
6 13 (물건의 무게, 물건의 가치)
4 8
3 6
5 12

 

dp	6/13 (물건 i)	4/8	3/6	5/12
1 (무게 j)	0	0	0
2	0	0	0
3	0	0	6
4	0	8 (4,2)	8
5	0	8	8
6	13	13	8
7	13	13	14

• 편의를 위해 [i][0], [0][j] 각 행과 열을 포함하지 않고 (1,1)부터 작성
• 위 dp배열에서 (1,1) 부분은 1의 무게일 때 6의 무게를 담을 수 없으니 0
• j = 6일 때는 첫번째 물건을 담을 수 있으니 13
• 이해가 되지않는 부분은 아마도 14의 값이있는 부분일텐데 어떻게 14라는 최적해가 도출되는지의 과정을 파악해야함.
  • (7,3)에서 무게가 7일 때 물건 i(3/6) 를 담을 수 있으니 이전 해와 현재 물건을 담았을 때의 값 비교가 진행됨
  • 이전 해(dp[i-1][j])는 13
  • 현재물건을 담았을 때의 값 = 현재물건 item[i][1]의 값 6 + 현재 물건을 담기위해 무게 3을 뺏을 때(7-3)의 이전 부분문제의 해
  • 현재 물건을 담았을 때의 가치가 더 크기 때문에 값 갱신
• 즉, 각 부분문제들의 해(dp배열)는 해당 무게일 때 담을 수 있는 최적해(최대가치)라는 것.
  • 위에서는 (4,2)의 부분문제 해를 사용하여 14라는 최적해를 도출

정리

• 위와 같이 기본적인 완전탐색 접근법으로는 O(2^N)이였던 시간복잡도를
• DP 메모이제이션을 활용하여 풀이하면 무게(K), 개수(N)에 대해 모든 배열을 채우는 과정인 O(KN)의 시간복잡도로 풀이가 가능.