dynamic programming

what?

문제를 sub-problem 으로 나누어 푸는 것.

dynamic programming?

• dynamic - multistage
• programming - decision making

원래의 문제를 보다 작은 문제들로 나누어서,
각 하위 문제(단계)마다 해법을 고안하는 것.

how?

knapsack problem

• 기타, 노트북, 시계가 있다.
• 부피와 가격은 순서대로 (3, 50$), (2, 200$), (1, 10$) 이다
• 4 만큼의 부피를 담을 수 있는 가방이 있다.

이 때, 가방안의 물건의 가치가 최대가 되도록 물건을 담으려면 어떻게 해야할까?

break down

나는 시계를 담을 수도 있고 안 담을 수도 있다. => true
(시계를 담았다) ---> 4부피가방최대가치 = 10 + 3부피가방최대가치(시계X)
(시계를 안담았다) ---> 4부피가방최대가치 = 4부피가방최대가치(시계X)

assembly

max(val_case_of 시계를 담았다,val_case_of 시계를 안담았다)

출처

https://en.wikipedia.org/wiki/Dynamic_programming