寻找一种清洁，高效的方式对一组数据的对阵已知模式

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的“定制包装”。我们已经有一个预定义的包装，其中包含A，B和C，称为Foo。因此，订单将是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（）来确定匹配，但随着预定义软件包的数量呈线性增长，我发现每种方式都会以指数方式增长。

我跑了一些其他编码器的朋友，再次，虽然它似乎应该有一个简单的答案，我们都发现它并不像看起来那么简单。所以，我想我会在这里发布它作为一个很好的面条担架。非常感谢您的时间！

Answer 1

这个问题通常是一个“难”（就计算复杂性而言）。事实上，它在我脑海中响起了一些钟声，它可能会降低到像Knapsack problem那样的经典算法问题之一，但我无法给它添加一个正确的名称。

但是，有了这么小的问题空间（他们只能挑选10个产品），只需要蛮力即可。当有人提交自定义构建时，只是递归地攻击它，并且看看哪一个是最好的。

也就是说，采取他们选择的组件，并首先尝试从它中删除“包1”的组件。如果可以的话，拿走其余的组件，并尝试从组件中取出“组件2”等。跟踪你发现的最佳解决方案。

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

---

编辑补充：

根据的可能性的数量和多久，这实际上需要运行，你可以想写我上述的代码，然后先走一步，预 - 为每种可能的组合计算所有解决方案。然后，当有人提交自定义构建时，您只需获取答案，而不是每次从头开始计算。

即使你不想预先计算所有这些，我建议把结果存储每次有人做了自定义生成，那么在未来，如果别人不一样自定义生成你没有重新计算解决方案。

Answer 2

我建议你让客户帮忙。在产品选择屏幕中，显示可用的包装套件，并让它们组合（适当定价，使得套件总数足以涵盖特殊处理）。

Answer 3

对不起，让你的问题更复杂一些。 :-)

虽然你可能会喜欢预先计算可能的解决方案，或有消费者实际上是从预定义的包自己选择：如果哪一个预定义的包装已不再是股票？

，如果没有什么存在的解决方案来完成，此时的顺序？您会随后发送部分订单吗？如果是这样的话：即使您知道稍后您可以选择预定义的包裹，您是否也会包含单件物品？

你真的确定预定义的软件包不会有一些“偏好”分配吗？像订购“ABCD”时预定义的软件包以及预定义的软件包“ABC”和“BCD”一样？例如，如果您知道预定义的包“ABC”通常缺货，那么可能会使“BCD”在可能的情况下成为首选。

所以：也许你需要使用一些模型中，你可以轻松地改变一些硬编码的规则，而不是试图找到一个自动化的解决方案。这当然可以是PHP本身。