3 ms·
In the little example they give on the side, why not sort all items by value density, high to low, then fit items until the knapsack is full? Not so simple for
by IgorPartola 14y ago
In the little example they give on the side, why not sort all items by value density, high to low, then fit items until the knapsack is full? Not so simple for multiple dimensions, but when does this not work in a single dimension case?
- praptak 14y agoThis greedy approach is in fact the basis for an approximation algorithm with a guaranteed ratio aproximation. Failure to reach optimum: 110 dollars 55 volume gets chosen over 2*(60 dollars 50 volume), assuming knapsack volume 100.