3 ms·
Feels a lot like a variation on the Knapsack problem, which is known to be NPC-Complete. If that's true (and I haven't verified it - that's your problem) then
by RiderOfGiraffes 17y ago
Feels a lot like a variation on the Knapsack problem, which is known to be NPC-Complete.
If that's true (and I haven't verified it - that's your problem) then you can use any of the variations on the greedy algorithm to get a reasonably good solution.
http://en.wikipedia.org/wiki/Knapsack_problem http://en.wikipedia.org/wiki/Knapsack_problem
- yannis 17y agoThanks, it is very similar actually, I followed the link and is the cutting stock problem http://en.wikipedia.org/wiki/Cutting_stock_problem http://en.wikipedia.org/wiki/Cutting_stock_problem, seems quite complex. Need to do more reading!