mysql - 如果一行的总和等于 X，则选择行

Question

我有一张 table ，上面放着元素及其“重量”，它看起来像这样:

items
-----

id          weight
----------  ----------
1           1
2           5
3           2
4           9
5           8
6           4
7           1
8           2

我想要得到的是一个总和(权重)恰好为 X，同时遵守插入顺序的组。

例如，如果我正在寻找 X = 3，这应该返回:

id          weight
----------  ----------
1           1
3           2

即使 id 7 和 8 的总和也是 3。

或者如果我正在寻找 X = 7 应该返回

id          weight
----------  ----------
2           5
3           2

虽然ids 1、3、6的和也是7。

我有点迷失在这个问题上，并且一直无法提出一个至少可以做类似事情的查询，但是仔细考虑这个问题，RDBMS 处理起来可能会变得极其复杂。这可以通过查询来完成吗？如果没有，查询数据库以获取最少数据量的最佳方式是什么？

编辑:正如 Twelfth 所说，无论它返回多少行，我都需要返回总和，所以如果我要求 X = 20，我应该得到:

id          weight
----------  ----------
1           1
3           2
4           9
5           8

Answer 1

这在 sql 中可能会变得非常困难。你试图做的是解决 knapsack problem ，这是不平凡的。

The knapsack problem is interesting from the perspective of computer science for many reasons:

• 背包问题的决策问题形式(能否在不超过重量 W 的情况下获得至少 V 的值？)是 NP 完全的，因此没有可能的算法既正确又快速(多项式时间)情况下，除非 P=NP。
• 虽然决策问题是 NP 完全问题，但优化问题是 NP 难问题，其求解至少与决策问题一样困难，并且没有已知的多项式算法可以判断给定的解决方案是否是最优(这意味着没有更大的解决方案，从而解决决策问题 NP-complete)。
• 有一个使用动态规划的伪多项式时间算法。
• 有一个完全多项式时间逼近方案，它使用伪多项式时间算法作为子程序，如下所述。
• 实践中出现的许多情况，以及来自某些分布的“随机实例”，仍然可以准确解决。