[TIL] 배낭 문제 Knapsack Problem

배낭 문제 Knapscak Problem 

최대 K 의 무게를 담을 수 있는 배낭 각기 다른 가치 V 를 가지고 W 의 무게인 N 개의 물건을
배낭에 최대한 가치가 높은 물건들로 담을 수 있는 조합을 찾는 문제 

 

만약 n개의 물건이 있을 때, 가능한 모든 조합을 만들기 위해서는 2^n개의 경우를 시도해 보아야 하고

그렇게 된다면 시간 복잡도는 O(2^n) 이기 때문에 Brute Force 는 적합하지 않다 

 

배낭 문제는 물건을 쪼갤 수 있는 Fraction Knapsack Problem 과
물건을 쪼갤 수 없는 0-1 Knapsack Problem 으로 나뉜다 

 

 

부분 배낭 문제 Fraction Knapsack Problem 

물건을 쪼개서 넣을 수 있다 

가치가 큰 물건부터 담고, 남은 무게만큼 물건을 쪼개는 방식 

그리디 알고리즘을 활용하여 해결할 수 있다 (최적해 보장)

 

부분 배낭 문제 접근 방식

1) 가치 V 를 무게 W 로 나누어 단위 당 가치를 구하고, 내림차순으로 정렬한다 

2) 단위 당 가치가 제일 높은 물건 순으로 배낭에 넣는다 

3) 배낭의 무게 K 가 남아 있는 경우, 그 다음 가치가 높은 물건을 쪼개어 넣는다

 + 쪼갠 물건은 그만큼의 가치도 변경된다, ex) 가치 5, 무게 5인 물건을 3만 담을 경우 가치도 5*(1/5*3) 하여 3이 된다

0-1 Knapsack Problem 

물건을 쪼개서 넣을 수 없다

동적 계획법, 백트래킹, 분기한정법을 활용하여 해결할 수 있다 

그리디 알고리즘으로 최적해를 보장하지 않는다 

 

0-1 배낭 문제 접근 방식

물건	1	2	3
무게	2	3	4
가치	3	4	5

1) 가방의 무게를 물건의 개수와 무게로 2차원 테이블을 만들고

  첫번째 물건부터 고려하여 각 무게마다 최적의 이익을 계산해 표에 기입한다 

2) 차례로 표를 채우면서 앞서 구했던 이익과 현재 이익을 비교하여 최적의 이익을 구한다 

		0	1	2	3	4	5
1번 물건 (무게 2, 가치 3)		-	-	3	3	3	3
2번 물건 (무게 3, 가치 4)		-	-	3 (1번)	4 (2번)	4 (2번 > 1번)	7 (1번+2번)
3번 물건 (무게 4, 가치 5)		-	-	3 (1번)	4 (2번)	5 (3번 > 2번)	5 or 7

 

동적 계획법 Dynamic Programming 으로 접근하기 

1) 재귀 관계식을 구하고 2) Bottom Up 방식으로 Table 을 만들고 Memoization 을 활용한다 

P[i][w] - 총 무게가 w 를 초과할 수 없다는 제약 조건 하에서 처음 i개 아이템에서만 선택할 때 얻는 최적의 이익
P[n][w] - n개의 아이템으로 얻을 수 있는 최대 이익 

동적 계획법 재귀 관계식

출처 https://www.youtube.com/watch?v=uWigKsbo3SU

 

이론은 여기까지만 정리하고 나머지는 문제를 풀어보면서 공부해 보려고 한다 

 

---

아주 평범한 배낭 문제를 두 가지 방법으로 풀었다 

https://helloahram.tistory.com/69