MySQLでPHPのサブセットサム問題

Question

次の問題：

私はそこに曲を持つMySQLデータベースを持っています。

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

は、ユーザーがPHPのフォームに特定の時刻を入力することができるはずとPHPの機能が彼に与えられた時間まで追加曲のすべての可能な組み合わせのリストを与える必要があります。データベースには、以下の構造を有します＆lt; X min。

したがって、ユーザーが1時間の音楽＆5分を聴きたい場合は、フォームに60分と5分のしきい値を入力し、可能なすべてのソングセットを受信して​​合計55〜65になります分。それは重複して印刷するべきではありません。

私はすでにこの問題のいくつかのアプローチを見つけましたが、曲名などではなくXまでの期間を返すだけでした。だから私の問題はこれを解決する方法です。所望の時間までに合った曲、または対応する曲名でリストをプリントアウトする。

This私が見つけた最高の回答のようですが、私は自分のデータベースに適用できません。

Answer 1

説明しているものはKnapsack Problemです。私が大学にいた時、私たちはDynamic Programmingを使ってこのような問題を攻撃しました。

brute-force方法（ただ1つ（またはそれ以上まで、すべての組み合わせを試してみてください）作品の複雑O(n!)、または階乗の長さの問題である！ - 極めてを反復処理し、計算することが長い

トラックのあなたの時間がある場合（秒で私に一番簡単な数学を思わ）intとして格納され、その後、あなたのナップザックサイズは3300から3900（3600秒== 1時間）である。

は、常に一致する最初セットを返すためにあなたの目標です常にraを返すndomセット？

_{^{注 - 袋サイズの境界を設定すると、可能な回答の数が大幅に増えます。}}