Knapsack algorithm, large capacity

Question

I'm currently in developing a playlist player and im facing a problem. I have gaps of variable length in my playlist that i want to fill with special audio files. These files also have a variable length, usually shorter then the gap i have in my playlist.

This sounds like a classic knapsack problem, so i tried to implement this algorithm. This works fine for smaller gaps, but whenever i have a gap of 30 minutes the algorithm uses extreme amount of memory. This is expected because im using dynamic programming to solve the problem.

The knapsack has a capacity of {gap in milliseconds} and the knapsack items have the weight of the audio files in milliseconds.

This is extremely innefficient. So i was wondering if i could use a different algorithm, or maybe change the weight and capacity into smaller variables. So far i was thinking of dividing everything by an arbitrary number, but il lose precision if i do so.

Anyone has any ideas?

Edit:

I have about 500 fillers to fill the gap. And changing the pitch is not possible. The set of fillers should have a perfect solution. I really want millisecond precision but I can live with under 100ms off.

Answer 1

You said play-list so I'm assuming you have songs, and a typical song is about 3 minutes so your solution will be about 10 songs. Thus you can divide all your times by 50 and then the typical error for a song will be plus or minus 25 milliseconds and so for 10 random songs the error will usually be about (25 milliseconds * sqrt(10)) < 100 milliseconds. If you want better guarantees on the error then you can divide your song times and target time by 20 or 10, but certainly if you divide your times by 10 then you should very, very rarely get an error above 100 milliseconds. And a divide by 10 means you divide memory by 10 for the exact O(WN) dynamic programming solution so it can make the difference between fitting into memory and not if you are on the borderline.