php - 寻找一种干净、高效的方法来将一组数据与已知模式进行匹配

Question

使用 php5.2 和 MySQL 4.1.22

我遇到过一些事情，一开始看起来很简单，但后来我却回避了一个简单、干净的解决方案。

我们有预定义的产品“包”。包装 1 中可能包含产品 A、B 和 C。包装 2 可能包含 A、C、D 和 G 等。包装的大小从 3 到 5 个产品不等。

现在，客户可以选择任意 10 种可用产品并制作“定制”包装。由于我们已经有了某些预定义的包，我们希望尽可能使用较小的现有包(为了便于运输)构建自定义包。

因此，例如，客户选择创建产品 A、B、C、D、E 和 F 的“自定义包”。我们已经有一个名为 Foo 的预定义包，其中包含 A、B 和 C。因此，顺序将是 Foo、D、E 和 F。

问题在于拥有最少数量的单个元素，其次是最少数量的包裹。例如:

定制包装:A、B、C、D、E、F、G、H、I、J。

预定义包 (1):A、B、C、D、E

预定义包 (2):A、B、C

预定义包 (3):D、E、F

如果我只取最大的匹配项，那么我有 1 (5pc) 个包裹和 5 个单独的项目。包 (2) 和 (3) 都不能用剩余的项目构建。

如果我看得更深，我发现通过不构建包 (1)，我可以构建包 (2) 和包 (3)。这意味着我有 2 个包裹和 4 个单独的元素(在此商业规则中是更好的选择)。

因为我使用的是 MySQL，所以我只能使用一层子选择(据我所知)。所以这种排序需要在 php 中执行。我研究过使用 array_intersect() 来确定匹配项，但随着预定义包的数量呈线性增长，我发现的每种方式在处理方面都呈指数级增长。

我和其他几个程序员 friend 一起跑过这个，虽然看起来应该有一个简单的答案，但我们都发现它并不像看起来那么简单。所以，我想我会把它贴在这里作为一个很好的面条担架。非常感谢您的宝贵时间!

Answer 1

该问题通常是“困难”问题(就计算复杂性而言)。事实上，它在我脑海中敲响了一些警钟，它可能会简化为那些经典的算法问题之一，比如 Knapsack problem。 ，但我无法为其附加专有名称。

然而，由于问题空间如此之小(他们只能选择 10 种产品)，暴力破解应该相当快。当有人提交自定义构建时，只需使用所有可能性递归地攻击它，看看哪个是最好的。

也就是说，拿他们选择的组件，首先尝试从中删除“Package 1”的组件。如果可能的话，取出剩余的组件并尝试从中取出“包 2”的组件，等等。跟踪您找到的最佳解决方案。

如果它仍然不够快(但我认为它可能会，这取决于你有多少预构建的包)，你可以应用一些 dynamic programming加快速度的方法。

---

编辑添加:

根据可能性的数量和实际运行所需的时间，您可能想要编写我上面描述的代码，然后继续为每个可能的组合预先计算所有解决方案。然后，当有人提交自定义构建时，您只需获取答案，而不是每次都从头开始计算。

即使您不想预先计算所有这些，我也建议您在每次有人进行自定义构建时存储结果，这样将来如果其他人进行相同的自定义构建，您就不必这样做了重新计算解决方案。