有表包含
ID Qty ---------- 1 2 2 4 3 1 4 5
现在,如果我必须选择数量总和等于10的行,
我怎样才能做到这一点 ？
喜欢2 4 1 = 7
但如果我加5然后12
所以忽略2,然后
4 1 5 = 10
我怎样才能做到这一点？
编辑：
我想要任何可能的组合,总结得到价值.
假设7然后是总计最多7行的任何行
如果8,那么任何行总计为8
想要具有组合等于给定值的行/行.
解决方法
您要解决的问题称为
subset sum问题.不幸的是,这是
NP-complete.
这意味着,无论您使用sql还是其他任何语言来解决问题,您都只能解决问题的非常小的实例,即表中只有少数条目的实例.否则,运行时将变得过多,因为它随着表中的行数呈指数增长.这样做的原因是找到解决方案基本上没有比尝试所有可能的组合更好的方法.
如果可以接受近似解,则存在多项式时间算法,其在维基百科页面上描述.
