sql - 如何获取总和等于给定值的行

Question

有表格包含

ID     Qty
----------
1       2
2       4
3       1
4       5

现在，如果我必须选择数量总和等于 10 的行，我该怎么做？

就像 2+4+1 = 7但如果我加 5 那么 12

所以忽略2，然后4+1+5 = 10

我怎样才能实现这个目标？

编辑:

我想要任何可能的组合，总之可以给出值(value)。假设 7 则任意行的总和为 7同样，如果 8 则任意行的总和为 8

想要组合等于给定值的行。

Answer 1

您要解决的问题称为 subset sum问题。不幸的是，它是NP-complete .

这意味着，无论您使用 SQL 还是任何其他语言来解决它，您都只能解决问题的非常小的实例，即表中只有几个条目的实例。否则，运行时间将变得过多，因为它随着表中的行数呈指数增长。这样做的原因是，基本上没有比尝试所有可能的组合更好的找到解决方案的方法了。

如果近似解可以接受，可以使用多项式时间算法，维基百科页面上对此进行了描述。