with with

0-1 Knapsack Promble은 각각의 가치(profit)와 무게(weight)를 갖는 여러 아이템을 가방에 추가하는데, 최대 가방이 담을 수 있는 무게를 초과하지 않는 범위에서 아이템의 가치가 최대가 되도록하는 아이템의 집합을 찾는 알고리즘이다. 이 문제를 접근하는 방법은 여러개가 있어 한 번에 소개해보고자 한다. Greedy Approach 그리디한 방법으로 해결하는 접근방식은 다음과 같다. 단위무게당 가격으로 내림차순 정렬을 하고, 무게가 가득 찰 때 까지 집어넣는 방식이다. 하지만 이 방식에는 문제가 존재한다. 바로 항상 최적해를 도출하지는 못한다는 것이다. 단, fractional knapsack problem의 경우에는 그리디한 방법으로도 최적해를 도출할 수 있다. (fractional..