0-1 Knapsack Problem 문제 : 라고 할 때, 를 만족하면서 가 최대가 되도록 가 되는 를 결정하는 문제이다. 무작정 (탐욕적) 알고리즘 개의 물건에 대해서 모든 부분집합을 다 고려한다. 그러나 불행하게도 크기가 인 집합의 부분집합의 수는 개 이다. 동적계획적인 접근 방법 𝑖> 0이고 𝑤>0일 때, 전체 무게가 𝑤가 넘지 않도록 𝑖번째 까지의 항목 중에서 얻어진 최고의 이익(optional profit)을 𝑃[𝑖][𝑤]라고 하면, 와 같다. 이때, 𝑃[𝑖 − 1][𝑤]는 𝑖번째 항목을 포함시키지 않는 경우의 최고 이익이고, 𝑝𝑖 +𝑃[𝑖−1][𝑤−𝑤𝑖]는 𝑖번째 항목을 포함시키는 경우의 최고 이익이다. 코드 실습은 아래 github 링크 참고해 주세요. https://github.com/o..
