[algorithms] ch6. Dynamic programming (Knapsack)

(23.03.30)

algorithms  S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기

http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf

 

 

정리한 내용

6.4 Knapsack

 

예전에 수업들으면서 정리했던 내용: https://hey-stranger.tistory.com/140

---

 

Knapsack

- 최대 무게가 정해져있는 배낭 안에 value가 최대가 되도록 물건을 담는 방법을 찾는 문제이다.

- knapsack은 중복을 허용하여 물건을 선택하는 경우와 중복을 허용하지 않고 물건을 선택하는 경우로 나누어 생각해 볼 수 있다.

 

---

knapsack with repetition

- 중복 선택 허용 o

 

 

knapsack with repetition 수행 예시

item이 1~4 까지 있으며 각각의 weight와 value는 위와 같다. 가방에 넣을 수 있는 최대 weight값은 10이다. 

 

K(0) 은 0으로 초기화하고 K(w)에서 w를 1부터 W(10)까지 늘려나가며 knapsack의 최대 value를 계산해본다.

 

---

knapsack without repetition

- 중복 선택 허용 x

 

 

 

 

knapsack without repetition 수행 예시

item이 1~4 까지 있으며 각각의 weight와 value는 위와 같다. 가방에 넣을 수 있는 최대 weight값은 10이다. 

 

j=0일 때는 모두 0으로 초기화 시켜주고, j=1, 2, ... , 4 로 하나씩 늘려가면서 최대 value 값을 찾아본다.

j=1일 때의 최대 value 계산 과정

 

j=2일 때의 최대 value 계산 과정

 

j=3일 때의 최대 value 계산 과정

 

j=4일 때의 최대 value 계산 과정

 

최종 결과는 아래와 같다. 

 

 

결과 테이블을 보고 knapsack 에 어떤 물건이 들어가는지 해석하기