2

次の問題:

曲を含むMySQLデータベースがあります。データベースの構造は次のとおりです。

id INT(11)(PRIMARY)
title VARCHAR(255)
album VARCHAR(255)
track INT(11)
duration INT(11)

ユーザーは特定の時間を php フォームに入力できる必要があり、php 関数は指定された時間 ±X 分になる曲のすべての可能な組み合わせのリストをユーザーに提供する必要があります。

したがって、ユーザーが 1 時間±5 分の音楽を聴きたい場合、フォームに 60 分と 5 分のしきい値を入力し、合計で 55 ~ 65 分になるすべての可能な曲セットを受け取ります。重複を出力するべきではありません。

私はすでにこの問題へのいくつかのアプローチを見つけましたが、それらは曲名などではなく、Xになるまでの期間のみを返しました。したがって、私の問題は、これを解決して追加する曲のIDを返す方法ですするか、対応する曲名のリストを印刷します。

これは私が見つけた最良の答えの 1 つに思えますが、データベースに適応させることができません。

4

1 に答える 1

0

あなたが説明しているのは、ナップザックの問題です。私が大学にいたとき、動的計画法を使用してこのような問題に取り組みました。

力ずくの方法(1 つ (または複数) が機能するまですべての組み合わせを試してみてください) は、複雑さO(n!)、または階乗長の問題であり、反復して計算するには非常に時間がかかります!

トラックの時間がint(私には秒単位が最も簡単な計算のように思えます) として保存されている場合、ナップザックのサイズは 3300-3900 (3600 秒 == 1 時間) です。

一致する最初のセットを常に返すことが目標ですか、それともランダムなセットを常に返すことが目標ですか?

注 - 袋のサイズを制限することで、可能な回答の数が大幅に増えます。

于 2011-09-14T15:10:10.957 に答える