寻找一种干净、有效的方法来将一组数据与已知模式进行匹配
使用 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() 来确定匹配，但我发现的每种方法在处理方面都呈指数增长，因为预定义包的数量呈线性增长。
我让其他几个程序员朋友再次运行了这个，虽然看起来应该有一个简单的答案，但我们都发现它并不像看起来那么简单。 所以，我想我应该把它作为一个漂亮的面条担架张贴在这里。 非常感谢您抽出时间！
Using php5.2 and MySQL 4.1.22
I've come across something that, at first, appeared simple but has since evaded me in regards to a simple, clean solution.
We have pre-defined "packages" of product. Package 1 may have products A, B and C in it. Package 2 may have A, C, D and G in it, etc. The packages range in size from 3 to 5 products.
Now, a customer can pick any 10 products available and make a "custom" package. Since we already have certain predefined packages, we'd like to build the custom package with smaller existing packages (for shipping ease) where possible.
So, for instance, a customer selects to create a 'custom package' of products A, B, C, D, E and F. We already have a predefined package that contains A, B and C called Foo. So, the order would then be Foo, D, E and F.
The catch is in having the least amount of individual items, followed by the least amount of packages. For instance:
Custom Package: A, B, C, D, E, F, G, H, I, J.
Predefined Package (1): A, B, C, D, E
Predefined Package (2): A, B, C
Predefined Package (3): D, E, F
If I simply take the largest match, then I have 1 (5pc) package and 5 individual items. Neither Package (2) nor (3) can be built with the remaining items.
If I look deeper, I find that by not building package (1) I can instead build package (2) and package (3). Which means I have 2 packages and 4 individual items (a better choice in this buisiness rule).
As I'm using MySQL, I'm under the restraint of only having one layer of sub select available (to my knowledge). So this sort will need to be performed in php. I've looked at using array_intersect() to determine matches, but every way I've found grows exponentially in regards to processing as the number of predefined packages grows linearly.
I ran this by a couple other coder friends and again, while it seemed like there should be an easy answer we all found that it wasn't as simple as it seems. So, I thought I'd post it here as a nice noodle stretcher. Thanks much in advance for your time!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
该问题通常是一个“困难”问题（就计算复杂性而言）。 事实上，它在我的脑海中敲响了一些警钟，它可能会简化为经典算法问题之一，例如 背包问题，但我无法为其附加正确的名称。
然而，由于问题空间如此之小（他们只能选择 10 个产品），暴力破解应该会相当快。 当有人提交自定义构建时，只需用所有可能性递归地攻击它，看看哪一个是最好的。
也就是说，取出他们选择的组件，并首先尝试从中删除“Package 1”的组件。 如果可能的话，取出剩余的组件并尝试从中取出“包 2”的组件，依此类推。跟踪到目前为止您找到的最佳解决方案。
如果它仍然不够快（但我认为可能会足够快，具体取决于您有多少预构建的软件包），您可以应用一些 动态编程方法来加速它。
编辑添加：
根据可能性的数量以及实际运行所需的时间，您可能需要编写我上面描述的代码，然后继续预先计算所有解决方案每种可能的组合。 然后，当有人提交自定义构建时，您只需获取答案，而不是每次都从头开始计算。
即使您不想预先计算所有这些，我建议每次有人进行自定义构建时都存储结果，这样将来如果其他人进行相同的自定义构建，您就不必重新计算解决方案。
The problem is generally a "hard" one (speaking in terms of computational complexity). In fact it rings some bells in the back of my head that it probably reduces to one of those classic algorithm problems like the Knapsack problem, but I can't attach a proper name to it.
However, with such a small problem space (they can only pick 10 products), it should be fairly quick to just brute-force the thing. When someone submits a custom build, just recursively attack it with all possibilities and see which one is the best.
That is, take the components they've selected, and first try to remove the components of "Package 1" from it. If that's possible, take the remaining components and try to take the components of "Package 2" from it, etc. Keep track of the best solution you've found so far as you go along.
If it's still not fast enough (but I think it probably will be, depending on how many pre-built packages you have), you could apply some dynamic programming methods to speed it up.
Edited to add:
Depending on the number of possibilities and how long this actually takes to run, you may want to write the code I described above, and then just go ahead and pre-compute all the solutions for every possible combination. Then when someone submits a custom build, you just have to fetch the answer instead of computing it from scratch every time.
Even if you don't want to pre-compute them all, I'd suggest storing the result every time someone does a custom build, then in the future if anyone else does the same custom build you don't have to recalculate the solution.
我建议你让客户帮忙。 在产品选择屏幕中，显示可用的包装套装，并让他们进行组合（适当定价，以便连体衣的总和足以覆盖特殊处理）。
I suggest you let the customer help. In the product selection screens, show what packaged sets are available, and let them make the combinations (priced appropriately so that the sum of onesies is enough to cover special handling).
抱歉，让你的问题变得更复杂了。 :-)
尽管您可能喜欢预先计算可能的解决方案，或者让消费者自己实际从预定义的软件包中进行选择：如果预定义的软件包不再有库存怎么办？
如果此时没有解决方案来完成订单怎么办？ 然后，您会运送部分订单吗？如果是的话：即使您知道稍后可以选择预定义的包裹，您是否会包含单个商品？
您真的确定预定义的包不会分配一些“偏好”吗？ 比如订购“ABCD”时选择哪个预定义包，并且存在预定义包“ABC”和“BCD”？ 例如，如果您知道预定义的软件包“ABC”经常缺货，那么也许“BCD”会尽可能成为首选。
所以：也许您需要使用一些可以轻松更改某些硬编码规则的建模，而不是尝试找到自动化解决方案。 这当然可能是 PHP 本身。
Excuse me for making your problem a bit more complicated. :-)
Though you might like pre-calculating possible solutions, or have the consumers actually choose from the predefined packages themselves: what if a predefined package is no longer in stock?
What if no solution exists to complete the order at this time? Would you then ship part of the order, and if so: would you include single items even if you know that at some later time you could select a predefined package?
And are you really sure that predefined packages will not have some "preference" assigned? Like which predefined package to select when ordering "ABCD" and predefined packages "ABC" and "BCD" exist? If, for example, you know that predefined package "ABC" is often out of stock, then maybe that will make "BCD" to be preferred whenever possible.
So: maybe you need to use some modelling in which you can easily change some hard-coded rules, rather than trying to find an automated solution. This could of course be PHP itself.