knapsack problem

작년.. 이 아니라 재작년 수업 때 배운 건데 완 전 까먹어서 문제 풀 때 써먹지 못했다ㅠ

 

 

• Fractional Knapsack
• 0-1 Knapsack

 

"배낭 채우기 문제" 로 알려져 있으며

위와 같이 두 종류로 분류될 수 있다.

제한된 무게를 담을 수 있는 배낭에 최대의 가치를 갖도록 보석을 넣어야 하는 문제이다

 

 

 

Fractional Knapsack

보석들이 쪼개질 수 있는(Fractional) 문제이므로

Greedy한 방식으로 풀이 가능.

 

 

 

0-1 Knapsack

보석들을 나눌 수 없는 경우이므로 Greedy로 풀이가 불가능하다.

따라서 이 때 DP(Dynamic Programming)을 사용하여 풀이한다.

DP는 기본적으로 

큰 문제를 작은 문제로 쪼개어 해결한다

라는 분할 정복 기법의 원리를 따르며,

이에 Memorization 이라는 기법(보통은 배열에 저장)을 더하여 연산의 개수를 줄일 수 있다.

 

 

---

https://blog.naver.com/ndb796/221233570962

20. 다이나믹 프로그래밍(Dynamic Programming)

 

https://gsmesie692.tistory.com/113

Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)