목록fractional knapsack (1)

내 맴

Greedy Algorithm - Fractional Knapsack Problem

- Fractional Knapsack n개의 물건과 1개의 배낭이 있다 물건 i의 무게는 W(i), 이익은 P(i), 배낭용량은 M까지 가능하다 물건들을 배낭에 섞어서 넣되, 무게가 M을 넘지 않으면서 이윤이 최대가 되도록 물건을 담는 방법? (물건을 잘라서 담을 수 있다) 예시 ) 이익, 무게 등 무엇을 기준으로 잡고 greedy algorithm을 수행할지에 따라 결과가 다르다. 그러나 Fractional Knapsack 문제에서는 물건의 무게당 이익이 큰것을 기준으로 잡고 Algorithm을 짜면 항상 최적의 이익을 얻을 수 있다. 단, 단위 무게 당 이익이 큰 순서대로 정렬이 되어있어야만 하며, 정렬이 되어있다면 Time complexity는 O(n)이 된다 그러므로 최대 이익은 31.5가 된다..
Algorithm/개념 공부 2020. 4. 9. 18:12
이전 Prev 1 Next 다음