So I came across a solution to the fractional knapsack problem in linear time here: http://algo2.iti.kit.edu/sanders/courses/algdat03/sol12.pdf

I'm not sure I understand the algorithm given. We choose a random element from the value/weight ratio array, but why do we first add elements whose value/weight ratio is equal to that of the element chosen? Can someone simplify the algorithm?


Adding items from $\mathcal{R}_2$ happens only if the total weight of items in $\mathcal{R}_1$ is less than the knapsack maximum weight. In this case there is no need to choose what to take and what not to take from $\mathcal{R}_1$, just take all; if the total weight of $\mathcal{R}_1$ is higher than the knapsack max weight, then you need to choose from this set under the same constraint, which has the same problem strucuture as the original problem, hence the recursion. In either case, the items of $\mathcal{R}_1$ are indeed taken with a higher priority than $\mathcal{R}_2$ and $\mathcal{R}_3$.

To summarize this algorithm:

  • first try to take all the items that has a higher value-per-weight. If these items are heavier than the knapsack max weight, then there is no need to consider items with lower or equal value-per-weight.

  • otherwise, after taking all the higher value-per-weight items, try taking items from the equal-value and lower-value groups, subject to the total weight capacity.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.