mysql查找小计

Question

编辑：

有人告诉我，让你们读书意味着我受到更少的关注。我很抱歉。这是一个更简单的版本：

比尔从一家商店获得了价值100美元的物品。

他想退还足够的物品，以便返回30美元。

该商店有一个回报系统，可以帮助他这样做。

这是他扫描物品后的数据：

       item ¦   price ¦

socks             4.00
cheap tv         22.00
book on tape      9.00
book on paper     7.00
party hats        3.00
picture frame    10.00
hammer            5.00
juicer           16.00
mysql guide      24.00

total items  ¦ total price ¦
            9   100.00

Option 1
===============
item ¦          price ¦
cheap tv        22.00
party hats       3.00
hammer           5.00
===============

Option 2
===============
item ¦          price ¦

socks            4.00
picture frame   10.00
juicer          16.00
===============

Option 3
===============
item ¦          price ¦

book on tape    9.00
hammer          5.00
juicer         16.00

我可能错过了一些选择，因为我把所有这些都做出了。

因此，最大的问题是：

有没有办法（可能是组，也许是）有一个查询可以返回可能的物品组合的查询？

谢谢！

一个

Answer 1

如果物品数量足够小，则可以用SQL强制施加这种情况。这可能很快写解决方案，但是您可能想做一些更聪明的事情。听起来像背包问题“ NP完成。

如果项目数量很大，则需要研究动态编程算法。您必须问自己这对您的应用程序有多重要。

如果项目数量相对较小，则可以使此功能爆炸。一个蛮力SQL语句（您要的是）找到匹配的1,2或3个项目的组合如下。如果这不令人满意，那么SQL也许不是此工作的正确工具。

SELECT
   i1.id AS id1,
   NULL AS id2,
   NULL AS id3,
   i1.amount
FROM
   items i1
UNION ALL
SELECT
   i1.id AS id1,
   i2.id AS id2,
   i3.id AS id3,
   i1.amount + i2.amount AS total
FROM
   items i1,
   items i2
WHERE
   i1.amount + i2.amount = 30 AND
   i1.id <> i2.id AND
   i1.id <> i3.id
UNION ALL
SELECT
   i1.id AS id1,
   i2.id AS id2,
   i3.id AS id3,
   i1.amount + i2.amount + i3.amount AS total
FROM
   items i1,
   items i2,
   items i3
WHERE
   i1.amount + i2.amount + i3.amount = 30 AND
   i1.id <> i2.id AND
   i1.id <> i3.id AND
   i2.id <> i3.id

在Oracle中，您将使用Cube函数将其转变为通用版本，而不确定MySQL等效版本。

Answer 2

您要要求所有总计$ 30的子集。

这听起来很像 子集总和问题, ， 和 背包问题, ，所以我强烈怀疑您可以通过简单的查询来做到这一点。您可能必须转向T-SQL，但即使那样看起来也可能很丑。

我认为编程是去这里的方式。

Answer 3

我认为小组无法做到。

我想不出一个更好的方法，要么以您选择的编程语言或存储过程找到/尝试所有排列。

如果您有30美元以上的物品，则可以省略它们。

如果您想要某些标准“最佳”选项，将会有所改进。

Answer 4

这个问题实际上是P/NP。例如，如果没有蛮力搜索，您可能找不到最合适的文章价格，如果您的客户商店很大 - 您可以发现搜索很长时间。

您可以使用一些现有的算法，这些算法可以为您提供很好的猜测，但我担心它们都是非SQL。

我建议对您的问题进行近似：

创建一个过程/查询，该过程/查询找到一篇最适合想要价格的文章，而不是为您拥有的新更改再次称呼它。不完美，但会做这项工作。