php - PHP 与 MySQL 中的子集和问题

Question

以下问题:

我有一个 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添加到所需时间的歌曲或打印出具有相应歌曲名称的列表。

This似乎是我找到的最佳答案之一，但我无法使其适应我的数据库。

Answer 1

您所描述的是 Knapsack Problem .我上大学的时候，我们用过Dynamic Programming来解决这样的问题。

brute-force方法(只需尝试每一种组合，直到一个(或多个)工作变得复杂 O(n!)，或阶乘长度问题 - 非常迭代和计算!

如果您的轨道时间存储为 int(以秒为单位对我来说似乎是最简单的数学)，那么您的背包大小为 3300-3900(3600 秒 == 1 小时)。

您的目标是始终返回匹配的第一个 集，还是始终返回一个随机 集？

_{^{注意 - 通过限制袋子的大小，您可以大大扩展可能答案的数量。}}