0-1 배낭 문제

💫 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 알고리즘보다 우수