그리디 알고리즘 -(3) Knapsack Problem

The 0-1 Knapsack Problem

n개의 items이 있을 때

S는 item들의 집합

wi는 i번째 item의 무게

pi는 i번째 iteml의 가치

W는 배낭에 담을 수 있는 최대 무게

-> item들을 배낭에 담아 최대의 가치를 만들도록 하는 것이 이 문제의 핵심

 

 

브루트포스로 해결하기

1. 모든 가능한 경우를 고려

2. 최대 무게를 넘는 경우는 버리기

3. 남아있는 것들 최대의 가치를 만드는 것을 선택

-> 탐색하는데 2^n번의 시간이 걸림  

 

 

그리디로 해결하기

1. 

(1) 가치 순서대로 아이템들 정렬

(2) 좋은 가치 순서대로 가방에 담기 

(3) 더 이상 못 담으면 종료

-> 최적해를 얻지 못함

 

2. 

(1) 가벼운 순서대로 아이템들 정렬

(2) 가벼운 순서대로 가방에 담기

(3) 더 이상 못담으면 종료

-> 최적해를 얻지 못함

 

3. 

(1) 단위 무게당 가치가 높은 순서대로 아이템들 정렬

(2) 순서대로 가방에 담기

(3) 더 이상 못담으면 종료

-> 항상 최적해를 얻지 못함

 

 

* Fractional Knapsack problem은 위의 3번 방법으로 항상 최적해를 구할 수  있다.

 

 

다이내믹 프로그래밍으로 해결하기

 

(1) 점화식 세우기

i번째 아이템을 넣을 수 있는 경우와 없는 경우

(2) 경곗값 채우기

(3) 테이블 채워나가기

총 시간복잡도: 세타 2^n