1

编辑：

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

比尔从一家商店买了价值 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

我可能错过了一些选择，因为这一切都是我编造的。

所以，最大的问题是：

有没有办法（可能使用 GROUP BY）有一个查询可以返回任何可能的项目组合？

谢谢！

一种

4

4 回答 4

2

您要求的所有子集总和正好为 30 美元。

这听起来很像子集和问题和背包问题，所以我强烈怀疑你可以用一个简单的查询来做到这一点。您可能不得不求助于 T-SQL，但即使这样也可能看起来很难看。

我认为编程是通往这里的道路。

于 2008-12-29T09:48:46.537 回答
1

如果项目的数量足够小，您可以使用 SQL 强制执行此操作。这可能是一个快速编写的解决方案，但您可能想做一些更聪明的事情。听起来像是NP完全的“背包问题”。

如果项目数量很大，您将需要深入研究动态规划算法。你必须问问自己这对你的申请有多重要。

如果项目的数量相对较少，您可以强制执行此操作。查找 1,2 或 3 个匹配项的组合的蛮力 SQL 语句（这是您所要求的）如下。如果这不令人满意，那么 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 是否等效。

于 2008-12-29T10:37:55.283 回答
0

我不认为 group by 可以做到。

我想不出比使用您选择的编程语言或使用存储过程查找/尝试所有排列更好的方法。

如果你有超过 30 美元的物品，你可以省略它们。

如果您想要通过某些标准获得“最佳”选项，将会有一些改进。

于 2008-12-29T09:40:01.627 回答
0

这个问题实际上是P/NP。例如，如果没有强力搜索，您可能无法找到最合适的商品价格，并且如果您的客户商店很大 - 您会发现该搜索非常持久。

您可以使用一些可以给您很好猜测的现有算法，但恐怕它们都是非SQL的。

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

创建过程/查询以找到最适合所需价格的一篇文章，然后再次调用它以获得新的更改。不完美，但会完成工作。

于 2008-12-29T11:31:31.150 回答