[알고리즘] 0-1 Knapsack Problem (배낭 문제)

0-1 Knapsack Problem

출처 : 위키백과

 

문제 :

라고 할 때,

 

를 만족하면서 

가 최대가 되도록

가 되는

를 결정하는 문제이다.

• 무작정 (탐욕적) 알고리즘
  • 개의 물건에 대해서 모든 부분집합을 다 고려한다.
  • 그러나 불행하게도 크기가 인 집합의 부분집합의 수는 개 이다.

동적계획적인 접근 방법

𝑖> 0이고 𝑤>0일 때, 전체 무게가 𝑤가 넘지 않도록 𝑖번째 까지의 항목 중에서 얻어진 최고의 이익(optional profit)을 𝑃[𝑖][𝑤]라고 하면,

Recursive Property

와 같다. 이때, 𝑃[𝑖 − 1][𝑤]는 𝑖번째 항목을 포함시키지 않는 경우의 최고 이익이고,  𝑝𝑖 +𝑃[𝑖−1][𝑤−𝑤𝑖]는 𝑖번째 항목을 포함시키는 경우의 최고 이익이다.

 

---

 

코드 실습은 아래 github 링크 참고해 주세요.

https://github.com/oneonlee/Computer-Science/tree/main/3.%20Algorithms/05.%20Dynamic%20Programming/Knapsack%20Problem

GitHub - oneonlee/Computer-Science: Introduction to Computer Science