0

私はVB.net2012を使用しており、コードで次のことを実行したいと考えています。

長さxのメディアアイテムのリストがあります。
リスト内の各アイテムの期間はyです。
合計期間がzの新しいランダムリストを作成したいのですが、アイテムはこの新しいリストに1回しか表示されません。

これを行うための最良の方法は何ですか？これが「リュックサック問題」に該当するかどうかはわかりません。いずれにせよ、擬似コードまたは実際のvb.netコードのいずれかを使用して、これを実現するための支援をお願いします。

4

2 に答える 2

1

私はあなたを誤解しているかもしれませんが、あなたlはペアのリストを持っていて、そのような（そうしよう）(item,x)のサブセットを見つけたいようです。ll'sum(l'.e.item) == z

残念ながら、あなたはNP完全であるサブセット和問題を記述しているので、それに対する既知の多項式解はありません。

リストがかなり小さい場合は、ブルートフォースを使用できます（すべての可能性を確認してください）。数値がすべて整数の場合、疑似多項式時間で実行される 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 に答える