4

使用 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 个（5 件）包裹和 5 个单独的物品。包 (2) 和 (3) 都不能用剩余的项目构建。

如果我更深入地研究，我发现通过不构建包 (1)，我可以构建包 (2) 和包 (3)。这意味着我有 2 个包裹和 4 个单独的物品（在这个商业规则中是一个更好的选择）。

当我使用 MySQL 时，我受限于只有一层子选择可用（据我所知）。所以这种排序需要在 php.ini 中执行。我已经研究过使用 array_intersect() 来确定匹配项，但是随着预定义包的数量线性增长，我发现的每种方式在处理方面都呈指数增长。

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

4

3 回答 3

4

这个问题通常是一个“困难”的问题（就计算复杂性而言）。事实上，它在我的脑后敲响了一些警钟，它可能会简化为像背包问题这样的经典算法问题之一，但我无法为其命名。

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

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

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

编辑添加：

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

即使您不想全部预先计算，我建议每次有人进行自定义构建时都存储结果，然后将来如果其他人进行相同的自定义构建，您不必重新计算解决方案.

于 2009-04-09T22:14:23.193 回答
0

我建议你让客户帮忙。在产品选择屏幕中，显示可用的包装套装，并让他们进行组合（适当定价，以便连体衣的总和足以涵盖特殊处理）。

于 2009-04-09T22:07:15.067 回答
0

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

尽管您可能喜欢预先计算可能的解决方案，或者让消费者自己从预定义的包中进行选择：如果预定义的包不再有库存怎么办？

如果此时不存在完成订单的解决方案怎么办？然后您会运送部分订单吗？如果是：即使您知道以后可以选择预定义的包裹，您是否会包含单个商品？

你真的确定预定义的包不会分配一些“偏好”吗？喜欢订购“ABCD”时选择哪个预定义包，预定义包“ABC”和“BCD”存在？例如，如果您知道预定义的包“ABC”经常缺货，那么这可能会使“BCD”尽可能成为首选。

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

于 2009-04-09T23:42:12.093 回答