0
$\begingroup$

I'm creating a tool where, given a list of N items that have a volume (v) and a price (p), it should produce a list L that optimally fits as much value as possible into a single bin with a fixed size V. L does not need to contain all N.

My current solution is a heuristic that simply sorts all the items by price-per-volume and iterates over all items, inserting it into the bin if it can. This produces mixed results, so I'm looking to a bin-packing variant to solve this. All of the examples of bin-packing I've seen only seem to optimize for reducing the number of bins.

Is there a specific name for the variant I've described here?

$\endgroup$
1
$\begingroup$

This is the knapsack problem. It is NP-complete, so there are no algorithms that are both efficient on all problem instances and always optimal, but there are many different techniques that yield different points in the tradeoff between computation time and quality of the solution.

$\endgroup$

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.