Fractional knapsack problem
-
[DP] [Algorithm] Fractional Knapsack AlgorithmData miner/Algorithm & Data structure 2020. 3. 26. 16:30
https://pongdangstory.tistory.com/487 이전 포스팅에서, Unfractional knapsack problem을 다루었다. 이번에는 가방에 물건을 담을 때, 물건의 일부를 담는 경우는 어떠할까? 믹서기 같은 물건의 경우, 믹서기를 쪼개면 그 기능을 다하지 못하기 때문에 쪼갤 수 없는 반면에, 초콜릿이라고 한다면, 초콜릿은 소분해서 담을 수 있고 그 가치도 그 소분한 가치만큼에 해당하기 때문에 쪼갤 수 있다. 이 경우 그리디 알고리즘의 접근법으로 비교적 간단히 풀 수 있다. 이전의 input과 동일하게 문제가 주어졌다고 가정하자. K는 가방에 담을 수 있는 최대 무게 상한선이다. 즉, 물건이든, 물건의 부분이든 이 K kg의 무게를 넘을 수 없다. stuff_array는 다음과..