0-1 배낭 문제

게시 2023/12/13 업데이트 2024/08/29

By mascari4615

26 분읽는 시간

0-1 배낭 문제

배낭에 어떤 물건을 담아야 최대 이익을 낼 수 있는지 알아내는 문제.

각 물건을 통째로 넣거나 아예 안 넣거나 택일해야 한다는 조건이 있을 때, 배낭의 용량을 넘지 않으면서 배낭에 담을 수 있는 물건들의 최대 이익이 얼마인지(정확하게는 최대 이익을 얻어내기 위해 어떤 물건을 담아야 하는지) 알아내는 문제

욕심쟁이 방법으로 해결할 수 없음
DC와 DP를 이용하여 해결

최적화 문제

@ TODO: Tex 괄호

n개의 물건 $ S = { Object_1, …, Object_n } $
각 물건의 무게 $ W = { w_1, …, w_n } where\ w_i > 0 $
각 물건의 이익 $ P = { p_1, …, p_n } where\ p_i > 0 $
각 물건이 배낭에 넣어지는 부분 $ X = { x_1, … x_i } where\ x_i = 0 or 1 $
배낭의 용량 $ M > 0 $
최적해 $ K(n, M) $ 은 $ \sum_{i = 1}^n p_i x_i $ 의 최댓값. 단. $ \sum_{i = 1}^n w_i x_i \le M $

Solve By Dynamic-Programming

물건의 무게에 양의 실수를 허용한다면 DP를 이용하는데 어려움이 있음 (why??)

무작위 기법
1. 가능한 모든 물건의 조합(2ⁿ개)을 구하고
2. 배낭의 용량을 초과하는 조합은 모두 제외한 다음
3. 남은 조합들 가운데 이익이 최대인 것을 찾음
최적 부분구조
- 배낭 용량 $ = M $ 이고 최적해 $ = K(n, M) $ 일 때, 최적해 상태의 배낭을 관찰
  1. $ object_n $ 이 배낭에 없다: 애초에 $ object_n $ 이 없는 상태에서 문제를 풀어도 같은 결과.
    - 즉, $ K(n, M) = K(n - 1, M) $
  2. $ object_n $ 이 배낭에 있다: 배낭에 $ object_n $ 을 미리 넣어둔 상태의 최적해와 동일.
    - 즉, $ K(n, M) = K(n - 1, M - w_n) + p_n $
  3. ∴ 최적 부분구조를 가짐
- 두 조건에 따른 부문제의 최적해를 이용하면 원래 문제를 해결 가능
  - i.e. $ M = 30, W = {5, 10, 25}, P = {150, 150, 200} $이 주어졌을 때 최적해 $ K(3, 30) $ ?
    - → 3번째 물건이 최적해의 배낭에 포함되지 않는다는 가정하의 최적해인 $ K(2, 30) $ 과 3번째 물건이 최적해의 배낭에 포함된다는 가정하의 최적해인 $ K(2, 5) + 200 $ 가운데 더 큰 값
- 부문제를 정의하는 형식
  - 연속된 행렬 곱셈, 최적 이진 탐색 트리의 부문제는 시작과 끝이 매우 중요
    - i.e. 부문제 $ M_i … M_j $ 에서 조금씩 $ i $ 와 $ j $의 차를 늘려 최종적으로 $ M_1 … M_n $의 최적해를 구함
  - 동전 거스름돈 문제, 0-1 배낭 문제는 부문제의 한쪽 경계는 언제나 일정
    - i.e. 부문제 $ { object_1 , … , object_i } $에서 조금씩 $ i $ 를 늘려 최종적으로 $ { object_1, … , object_n } $ 에 대한 최적해를 구함
    - 부문제가 항상 $ K(1, j, m) $ 으로 정의되기 때문에 상수 부분을 제외한 $ K(n, M) $ 으로도 충분

@ KP_A

문제의 순환적 정의
- 최종 목표: 최대 이익을 가져다 주는 물건의 조합
- 최우선 목표: 최대 이익
  - $ n $ 개의 물건이 주어지고 배낭 용량이 $ M $ 인 0-1 배낭 문제의 최적해 $ K(n, M) $
    - $ object_n $이 배낭에 포함되지 않는다는 가정하의 최적해와 포함된다는 가정하의 최적해 중 더 큰 값
    - $ K(n, M) = Max { K(n - 1, M), K(n - 1, M - w_n) + p_n } $
- 일반화
  - $ i $ 개의 물건이 주어지고 배낭 용량이 $ w $ 인 0-1 배낭 문제의 최적해 $ K(i, w) $
    - $ object_i $ 가 배낭에 포함되지 않는다는 가정하의 최적해와 포함된다는 가정하의 최적해 중 더 큰 값
    - 물건이 없거나 배낭 용량이 0 → 최적해가 0
    - $ object_i $ 의 무게가 배낭의 용량을 넘어서는 상황 → $ object_i $가 최적해의 배낭에 포함되지 않을 경우만 고려

\[K(i, w) = \begin{cases} 0, if (i = 0 or w = 0) \\ K(i - 1, w), if (w < w_i) \\ max(K(i - 1, w), K(i - 1, w - w_i) + p_i), o.w. \end{cases}\]

  
// w[]와 p[]는 각 물건의 무게와 이익을 담은 배열
int DC_01_ks(int i, int w)
{
    if (i == 0 || w == 0)
        return 0;
    
    if (w < W[i])
        return DC_01_ks(i - 1, w);
    
    return Math.Max(DC_01_ks(i - 1, w), DC_01_ks(i - 1, w - W[i]) + P[i]);
}

중첩된 부문제와 DC
- 복잡도 ∝ 트리에 있는 노드 수 = 최대 $ \sum_{l = 1}^n 2^l $ = 최대 $ 2^{2 + 1} - 1 = O(2^n) $
  - 무작위 기법 $ Ɵ(2^n) $ 과 비슷, but 실제로 호출되는 노드 수는 보통 이보다 적음
  - 알고리듬을 개선하면 단말 노드 호출을 없앨 수 있음
- 중첩된 부문제 특성
  - 물건 개수가 많을수록 배낭 용량이 작을수록 부문제가 중복될 가능성이 커짐

@ KP_B

@ 가방 공간이 적어서 계산하지 않는, 부문제가 하나 밖에 없는 케이스가 생길 수 있음

DP로 풀기: 함수 대신 배열로

DP 1 - 알고리듬

최우선 목표: $ n $ 개의 물건과 배낭 용량이 $ M $ 인 0-1 배낭 문제의 최대 이익 $ K(n, M) $
2차원 배열의 원소 $ K[i][w] $ 에 $ K(i, w) $의 값을 저장하고 필요할 때마다 재사용
1차원 배열의 원소 $ P[i] $ 과 $ W[i] $ 에 각각 $ object_i $ 의 이익과 무게가 저장

@ KP_C
@ KP_D
@ 배열 B가 반드시 있어야 하나? 없어도됨 근데 일단 하던데로 계산하려고

DP 1 - 구현

  
// W[ ]와 P[ ]는 각 물건의 무게와 이익을 담은 배열
int _01_ks_DP(int n, int M)
{
    int[][] K = new int[MAX][MAX];

    for (int w = 0; w <= M; w++)
        K[0][w] = 0;
    for (int i = 0; i <= n; i++)
        K[i][0] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int w = 1; w <= M; w++)
        {
            if (w < W[i])
                K[i][w] = K[i - 1][w];
            else
                K[i][w] = Math.Max(K[i - 1][w], K[i - 1][w - W[i]] + P[i]);
        }
    }
    return K[n][M];
}

DP 1 - 분석

복잡도: $ Ɵ(nM) $ vs. DC의 복잡도 $ O(2^n) $
- 어느 쪽의 성능이 더 좋은가?: “알 수 없다”
  - M의 값이 매우 크면 DC의 성능이 더 나을 수도 있음
  - 예) $ M = O(n!) $ 이면 DP 1은 $ O(n!) $

DP 2 - 알고리듬

DP 1은 M이 n에 비해 큰 경우 재사용되지 않을 계산을 너무 많이 한다. 실제로 꼭 필요한 배열 원소만 계산할 수만 있다면!!
$ K[i][w] $ 를 계산하는데 $ K[i - 1][w] $ 와 $ K[i - 1][w - W[i]] $ 라는 이전 행의 두 값만 필요
- ∴ 계산될 배열 원소들을 확인한 후 꼭 필요한 원소만 계산

@ KP_E

DP 2 - 분석

개선된 알고리즘의 복잡도
- 실제 계산되는 배열 원소의 수에 비례
  - $ K(n, M) $ 을 구하기 위해 계산하는 배열 원소의 수는 행을 거슬러 올라가며 최대 2배씩 늘어난다고 할 때 $ \sum_{l = 1}^n 2^{l - 1} = 2^n - 1 $개: 최악의 경우 $ Ɵ(2^n) $
- 그러나, 저장되는 원소갯수는 배열 원소갯수보다 많을 수 없음
  - KP_F에서 칠해진 원소들이 계산 대상이라 한다면 그 숫자는 $ Ɵ(nM) $
  - 모든 물건의 무게가 1이고 n ≒ M일 경우에 해당
- 두 가지 관점 중 유리한 걸로 생각하면 되므로 $ O(minimum(2^n, nM)) $

@ KP_F

DP 3 - 알고리듬

지금까지 살펴본 DP 알고리즘은 물건 무게나 배낭 용량이 실수인 경우에는 사용 불가
- “원칙에 충실하자”
  - 이산 정보인 정수 대신 연속 정보인 실수를 처리하도록 개선
  - 이산 정보를 표현하는 도구인 배열 대신 연속 정보를 표현하는 도구인 함수에 초점
함수 $ K(i, w) $ 의 순환 정의(revisited)
- @ KP_G
- 입력으로 물건과 배낭 무게가 주어지면 유일한 출력값으로 최대 이익을 생성
- 어떤 모습의 그래프?: 입력 변수가 둘이므로 3차원 그래프로 나타내어야 함
- 이해하기 쉽도록 $ K(i, w) $ 를 여러 2차원 함수로 쪼개보자
  - $ i $ 는 정수, $ w $ 는 실수이므로 각 $ i $ 에 대해 서로 다른 함수 $ K_i(w) $ 를 정의하는 것이 타당
  - $ K_i(w): { object_1, …, object_i } $ 에 대해 $ x $ 축은 배낭 무게를, $ y $ 축은 최대 이익을 나타내는 함수
  - $ K_0(w), K_1(w), …, K_i(w), …, K_n(w) $ 를 정의하는 것이 가능
  - $ K_n(w) $ 를 구할 수 있다면 우리가 원하는 최적해인 $ K_n(M) $ 의 값을 계산 가능
0-1 배낭 문제의 순환 정의 함수 $ K(i, w) $ 를 함수 $ K_i(w) $ 로 재정의
- @ KP_H
- $ K_0(w) = 0 $
- 함수 $ K_{i - 1}(w - w_i) + p_i $ 는 $ K_{i - 1}(w) $ 를 $ x $ 축으로 $ w_i $ 만큼, $ y $ 축으로 $ p_i $ 만큼 평행 이동한 것
- 조건에 따라 $ K_{i - 1}(w - w_i) + p_i $ 과 $ K_{i - 1}(w) $ 를 하나로 합치면 $ K_i(w) $ 를 구할 수 있음
- → 수학적 귀납법에 의해 $ K_n(w) $ 를 유도 가능
  - $ K_0(w) = 0 $ 이다. 이를 평행 이동하여 $ K_0(w - w_1) + p_1 $ 를 구한 후 $ K_1(w) $ 를 얻는다.
  - $ K_1(w) $ 를 평행 이동하여 $ K_1(w - w_2) + p_2 $ 를 구한 후 $ K_2(w) $ 를 얻는다.
  - …
  - $ K_{i - 1}(w) $ 를 평행 이동하여 $ K_{i - 1}(w - w_i) + p_i $ 를 구한 후 $ K_i(w) $ 를 얻는다.
  - …
  - $ K_{n - 1}(w) $ 를 평행 이동하여 $ K_{n - 1}(w - w_n) + p_n $ 을 구한 후 $ K_{n}(w) $ 를 얻는다.

@ U 기말고사 출제 예상: y축 평행 이동으로 구하는 방법
@ KP_I

알고리즘
- 접근 방법: “원칙에 충실하자”
- 연속 정보를 표현하는 도구인 함수를 이산 정보를 이용하여 표현
- 각 $ K_i(w) $ 함수의 그래프는 구간에서만 연속인 계단식의 형태
- 따라서 각 구간의 시작점 좌표를 순서 리스트로 관리
- 예) [그림 4.15]의 (d)는 구간이 2개이므로 시작점 순서 리스트 $ {(5, 4), (8, 5)} $
핵심 아이디어: “ $ K_{i - 1}(w) $ 를 평행 이동하여 $ K_{i - 1}(w - w_i) + p_i $ 를 구한 후 $ K_i(w) $ 를 얻는다.”
- $ S_{i - 1}: K_{i - 1}(w) $ 의 시작점 리스트, $ SP_{i - 1}: K_{i - 1}(w - w_i) + p_i $ 의 시작점 리스트
- 목표: $ S_0 $ 에서부터 출발하여 $ S_n $ 을 구하는 것
- _
  1. $ K_{i - 1}(w) $ 를 평행 이동하여 $ K_{i - 1}(w - w_i) + p_i $ 를 구하려면 $ S _{i - 1} $ 의 각 좌표에 $ (w_i, p_i) $ 를 더함
  2. $ K_{i - 1}(w) $ 과 $ K_{i - 1}(w - w_i) + p_i $ 를 이용하여 $ K_i(w) $ 를 얻으려면 $ S_{i - 1} $ 와 $ SP_{i - 1} $ 를 합병하여 $ S_i $ 생성
- 기본적으로 정렬된 리스트를 하나로 합치는 작업
- 단 합병 시 두 원소 (x1, y1), (x2, y2)사이에 x1 ≥x2이고 y1 ≤ y2인 관계라면 (x1, y1) 제거

@ KP_J

각 함수는 정렬된 정점 리스트
원래는 최대한 많은 점을 기억해서 원래 함수의 모습을 기억하는 것이 좋은데, 게단식 그래프를 가지는 이런 상황에서는 단순히 점 몇 개 만을 기억하고도 x에 대한 y 값을 알아낼 수 있음

각 물건에 대해서는, 각 함수에 물건의 무게와 가치를 평행이동한 것으로

그리고 이전 함수와 평행 이동한 함수를 하나의 리스트로 합친다, 두 리스트는 정렬되어있다 (계단식) (정렬된 두 리스트를 하나로 합하기? => 합병 정렬)

각 x와 y값을 비교,
좌표 A와 B에 대해, x y가 둘 다 작은 좌표가 그래프에 그려지고,
x나 y 중 하나만 작은 경우에는, A와 B 중 x가 더 큰 쪽에 정렬과정에서 제외가 된다 (왜냐하면 x가 더 작은 쪽이 그 x보다 큰 값도 설명할 수 있으니까)

$ S_0 $, 평행이동 $ SP_0 $,
합치고 $ S_1 $, 평행이동 $ SP_1 $,

Solve By BackTracking

$ p_i/w_i > p_{i + 1}/w_{i + 1} $

BT에서는 요소 내림차순 정렬 조건이 붙음

Backtracking 최적화 문제 해결을 위한 구조 (링크 참고)

상태 공간 트리

주요 변수
- weight = 현재까지 담은 물건의 무게 합
- profit = 현재까지 담은 물건의 이익 합
- max_profit (optimal) = 현재까지의 최적해 즉 현재까지의 최대 이익
최적해를 변경하는 조건
- 배낭에 물건을 넣어야 하는 노드를 방문 → weight와 profit의 값이 증가
- 배낭의 용량을 넘어서지 않으면서 지금까지의 최대 이익보다 큰 이익이 발생하면 max_profit 값은 변경된 profit 값으로 바뀌어야 함
- 따라서 다음 조건을 만족하면 최적해가 변경
- $ (weight \le M) ^(and) (profit > max\ profit) $

@ TODO: and 기호

BT - 알고리듬

유망하지 않은 노드의 판별(현재 i번째 물건까지 결정된 상태)
- 규칙 1) 더 이상 물건을 담을 수 없는 경우, $ weight \ge M $
- 규칙 2) 아직은 배낭에 여유가 있지만 현 상태에서 어떻게 진행하더라도 현재까지의 최대 이익보다 더 큰 이익을 기대하지 못하는 경우(현재까지 담은 물건의 이익에다가 남아있는 물건들을 최적으로 추가하여 얻을 수 있는 이익을 합한다 하더라도 현재까지의 최대 이익을 능가하지 못하는 경우)
  - 부분 배낭 문제로 풀었을 때의 최대 이익 >= 0-1 배낭 문제로 풀었을 때의 최대 이익
    - ∴ 최대 이익의 상한을 구하기 위해 부분 배낭 문제로 변신
  - 현재까지 담은 물건의 이익($ profit $) + 남은 물건을 대상으로 부분 배낭 문제로 전환하여 풀었을 때의 최대 이익($ exp\ profit $)이 현재까지의 최대 이익($max\ profit$)보다 작다면 절대로 유망할 수가 없음 → 처음에 물건을 단위 무게 당 이익의 순에 따라 내림차순으로 정렬한 이유
    - $ profit + exp\ profit \ge max\ profit $
    - @ 배낭 0001

@ KP_0000
@ KP_0001

Back-Tracking, 실제로 트리를 만들지는 않고, 각 레벨에 해당하는 상태 정보를 배열에 저장한다.

배열을 이용하여 상태 공간 트리를 관리하는 방법
- 부분 집합의 합 문제와 동일
- 기억해야 할 정보는 “걸어온 길”
- 레벨 i 노드는 i 개 물건가운데 배낭에 넣은 물건들을 기억해야 함
  - 해당 노드가 유망하여 자식 노드로 내려간다면 i+1개 물건가운데 배낭에 넣은 물건들을 기억
  - 유망하지 않아 부모 노드로 백트래킹한다면 i -1개 물건가운데 배낭에 넣은 물건들을 기억

인덱스	1	2	3	4
포함여부	false	true	true	-

단말 노드가 아닌 노드가 해답이라면 해답 노드의 레벨까지 저장된 값만이 유효

배열 인덱스: 물건
배열 값: 물건의 포함 여부

∴ n 개의 값(true/false)을 저장할 수 있는 1차원 배열이 필요

BT - 구현

_01_ks_BT(0,0,0) 을 호출함으로써 시작
전역 변수 max_profit의 초기값은 0

  
void _01_ks_BT(int i, int profit, int weight)
{
    if (weight <= M && profit > max_profit)
    {
        max_profit = profit;    // 최대 이익의 변경 
        optimal = (X[1]..X[i]); // i 개의 물건들의 포함 여부
    }

    if (Promising(i, profit, weight))
    {
        X[i + 1] = true;
        _01_ks_BT(i + 1, profit + P[i + 1], weight + W[i + 1]);
        X[i + 1] = false;
        _01_ks_BT(i + 1, profit, weight);
    }
}

bool Promising(int i, int profit, int weight)
{
    int k, exp_weight = 0;
    float exp_profit = 0;

    // 꽉 차거나 찢어짐
    if (weight >= M)
        return false;

    for (k = i + 1; k <= n; k++)
    {
        if (weight + exp_weight + W[k] > M)
            break;
        exp_weight += W[k];
        exp_profit += P[k];
    }

    if (k <= n)
        exp_profit += (M - (weight + exp_weight)) * P[k] / W[k];

    if (profit + exp_profit <= max_profit)
        return false; 

    return true;
}

BT - 분석

상태 공간 트리의 노드 수

\[1 + 2 + 2^2 + … + 2^n = 2^{n+1} - 1\]

부분집합의 합 문제와 상태 공간 트리가 동일
NP-완전 문제 중에는 비교적 노드수가 적지만 여전히 지수 복잡도

유망한 노드 수

유망한 노드 개수를 계산할 수 없음
같은 개수의 노드를 갖더라도 배낭 용량이나 물건 무게에 따라 유망한 노드의 수가 달라짐
최적화 문제 → 상태 공간 트리를 모두 뒤져야 함. 단지 탐색하는 노드의 수가 달라질 뿐

DP vs. 백트래킹

Horowitz와 Sahni의 명저 “Fundamentals of Computer Algorithms”에는 Venkatesh가 실제 컴퓨터상에서 실행시켜 본 결과가 수록: 다음 4가지 경우의 데이터 집합 사용
- ➊ 각 물건의 무게와 이익을 1~1,000 범위 안에서 임의로 생성한 경우
- ➋ 각 물건의 무게와 이익을 1~100 범위 안에서 임의로 생성한 경우
- ➌ 각 물건 무게를 1~100 범위 안에서 임의로 생성하고 이익은 무게에 10을 더한 경우
- ➍ 각 물건 무게를 1~100 범위 안에서 임의로 생성하고 이익은 무게에 1.1을 곱한 경우
- 배낭 용량 M은 물건 무게의 합에 절반이 되도록 하고 물건의 개수 n에 대해 10개씩의 인스턴스에 대한 측정값을 비교 → 일반적으로 백트랙킹 알고리즘이 DP 알고리즘보다 우수

컴퓨터, 알고리즘

0-1 배낭 문제

Solve By Dynamic-Programming

DP 1 - 알고리듬

DP 1 - 구현

DP 1 - 분석

DP 2 - 알고리듬

DP 2 - 분석

DP 3 - 알고리듬

Solve By BackTracking

상태 공간 트리

BT - 알고리듬

BT - 구현

BT - 분석

상태 공간 트리의 노드 수

유망한 노드 수

DP vs. 백트래킹

인기 태그