Optimization Problem

[C1]

Im sure that this exists, but where?

How can M out of N song titles be selected to best fit (ie, minimize remaining available time) on a linear tape (reel recorder)?

There should be a ready to go algorithm for this. Does anyone know where it would be?

So a friend who collects music feels that it is critical to best fill the remaining available record time when archiving to reel-to-reel tape. So pick the best combination of M out of N songs on an LP to closest fit the end of the tape (ie, minimize the available record time remaining).

I believe that Ive seen this provided somewhere already as a calculator (but not recently).

 

[esun]

This is a variant of the Knapsack problem:

http://en.wikipedia.org/wiki/Knapsack_problem

This is a classic NP-complete problem, but if M and N are small it shouldn't be too bad.

 

[C1]

Youre right & actually that helps a lot so thanks. I think N<=12 should be enough and hopefully I have this algorithm ready to go in the Woolsey's "Quick & Dirties" handbook.
(Been a long ass time since I took LP/OR Methods.)

 

[Cogman]

Generally for optimization problems (Most of which are usually knapsack variant), I would recommend a genetic algorithm. Essentially, you are just picking random combinations and taking the best. (True genetic algorithms have breading ect.) Even though it sounds crazy, it usually converges on an optimal solution very quickly.

 

[blinblue]

EDIT: Whoa, very much the wrong thread here. Sorry about that