php - 使用 MySQL 的 PHP 中的子集和问题

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

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

Answer 1

你所描述的是一个背包问题。当我在大学时，我们使用动态编程来解决这样的问题。

蛮力方法（只需尝试每种组合，直到一个（或多个）工作是一个复杂性O(n!)或阶乘长度问题 -迭代和计算非常冗长！

如果您的曲目时间存储为int（以秒为单位对我来说似乎是最简单的数学运算），那么您的背包大小为 3300-3900（3600 秒 == 1 小时）。

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

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