0

我正在使用 VB.net 2012 并希望在代码中执行以下操作：

我有一个长度为 x 的媒体项目列表。
列表中的每个项目的持续时间为 y。
我想创建一个总持续时间为 z 的新随机列表，并且这些项目只能在这个新列表中出现一次。

做这个的最好方式是什么？我不确定这是否属于“背包问题”。无论哪种方式，我都可以使用伪代码或实际的 vb.net 代码来帮助实现这一点吗？

4

2 回答 2

1

我可能会误解你，但似乎你有l一对列表，(item,x)你想找到一个子集l（让它成为l'）这样sum(l'.e.item) == z。

不幸的是 - 您正在描述子集和问题，它是NP-Complete，因此没有已知的多项式解决方案。

如果列表很小，您可以使用蛮力（检查所有可能性）。如果数字都是整数， 还有一个DP 解在伪多项式时间内运行。
一些替代方法是近似算法或启发式算法 - 例如遗传算法。

于 2012-12-04T05:55:44.073 回答
0

伪代码：

1. Object Song: properties Name, Duration
2. mlstLibrary = List(Of Song) ... fill mlstLibrary
3. user enters desired playlist duration intPlaylistDuration    
4. make a copy of mlstLibrary called mlstLibraryWorking
5. Dim intPlaylistDurationWorking As Integer = 0
6. Dim lstPlaylist As New List(Of Song) ' This is the output playlist
7. Do While mlstLibraryWorking.Count > 0
7a.  Go through mlstLibraryWorking and remove all items that have .Duration > (intPlaylistDuration - intPlaylistDurationWorking)
7b1.  Pick random Song from mlstLibraryWorking 
7b2.  Add selected Song to mlstPlaylist
7b3.  intPlaylistDurationWorking += selected Song.Duration
7b4.  Remove selected Song from mlstLibraryWorking  
8. Loop
于 2012-12-04T06:30:09.543 回答