揹負算法，大容量

我目前正在開發一個播放列表播放器，而我正面臨一個問題。我的播放列表中有可變長度的空白，我想填充特殊的音頻文件。這些文件也具有可變長度，通常比我在播放列表中的間隙短。揹負算法，大容量

這聽起來像一個經典的揹包問題，所以我試圖實現這個算法。這適用於較小的差距，但每當我有30分鐘的差距時，該算法會使用極大的內存量。這是預期的，因爲即時通訊使用dynamic programming來解決問題。

揹包的容量爲{以毫秒爲單位}，揹包項目的音頻文件的權重以毫秒爲單位。

這是非常無效的。所以我想知道如果我可以使用不同的算法，或者可以將重量和容量改變成更小的變量。到目前爲止，我正在考慮用任意數字來劃分一切，但如果我這樣做的話，我會失去精確度。

任何人有任何想法？

編輯：

我有大約500個填充填補空白。而改變球場是不可能的。填料組應該有一個完美的解決方案。我真的想要毫秒精度，但我可以在100毫秒以內生活。

來源

2014-04-16 Terraego

你需要毫秒級的準確度嗎？如果是這樣，爲什麼？你是否控制了差距的長度？有點上下文很長。 – patros

缺口*有*是否被最佳填充？也許你應該停下來，當新的差距低於一定的閾值。 – Geobits

這聽起來很奇怪。 30分鐘的差距從哪裏來？爲什麼它必須完美匹配？音頻文件可以很容易地被拉伸百分之幾，沒有任何明顯的差異，也許這有助於？ – pentadecagon

你說的播放列表，所以我假設你有歌曲，一首典型的歌曲約3分鐘，所以你的解決方案將約10首歌曲。因此，您可以將所有時間除以50，然後一首歌曲的典型錯誤將爲正負25毫秒，因此對於10首隨機歌曲，錯誤通常大約爲（25毫秒* sqrt（10））012毫秒。如果你想對錯誤有更好的保證，那麼你可以將你的歌曲時間和目標時間除以20或10，但是當然如果你將你的時間除以10，那麼你應該很少，很少會在100毫秒以上得到一個錯誤。除以10意味着您將精確的O（WN）動態編程解決方案的內存除以10，這樣就可以區分如何在內存之間進行匹配，而不是在邊界線上。

來源

2014-04-16 21:00:32 user2566092

這就是我現在所用的，似乎我無法進一步改進算法。我會嘗試一些不同的數字，看看什麼效果最好！ – Terraego

您可以使用迭代加深逼近，其中填充所有最長填充符合的間隙。然後刪除它們（縮短到更長），在每個之後用動態算法解決剩餘空間。由於每次移除都會增加剩餘間隙的長度，所以每個問題都會變得更加困難。一旦你用完時間或記憶，停止使用最後生成的解決方案。

來源

2014-04-16 16:49:07 Sneftel

揹負算法，大容量

回答

相關問題