[알고리즘] Knapsack problem:dynamic programming

(2021.10.14)

알고리즘 수업들으면서 정리하기 13탄

7주차 보충강의내용- Knapsack problem

(보충강의 있는지 모르고 실강 전에 안들었다..)

---

 

Knapsack problem:dynamic programming

문제: item 여러개가 있는데, 그 item은 각각의 value와 weight를 가진다. knapsack은 W(kg)까지 수용할 수 있다. 이때, knapsack에 담을 수 있는 최대 value가 무엇인가??

 

 

 

우선, 이 문제를 navie approach로 풀어본다면

각각의 item을 순서대로 넣을지 말지를 결정하기 때문에 2 x 2 x ... x 2=2^n 의 시간이 걸린다.

--> O(n^2)

 

 

 

Dynamic programming 의 4단계를 거쳐 문제를 풀어볼 수 있다.

1. Characterize the structure of an optimal solution
2. Recursively define the value of an optimal solution
3. Compute the value of an optimal solution, typically in a bottom-up fashion
4. Construct an optimal solution from computed information

 

 

 

1. Characterize the sturcture of an optimal solution

 

 

 

 

 

2. Recrusively define the value of an optimal solution

 

 

 

 

 

3. Computed the value of an optimal solution, typically in a bottom-up fashion

 

table의 요소를 채우는 코드

 

 

 

4. Construct an optimal solution from computed information

 

Knapsack의 time complexity