Looking for a clean, efficient way to map a dataset to known patterns

Question

Using php5.2 and MySQL 4.1.22

I came across something that at first seemed simple, but has since deviated from me regarding a simple, clean solution.

We have predefined product packages. Package 1 may contain products A, B, and C. Package 2 may have A, C, D, and G therein, etc. Packages have a size of 3 to 5 products.

Now the client can choose any 10 available products and make a "custom". Since we already have certain predefined packages, we would like to create a custom package with smaller existing packages (for ease of delivery) where possible.

So, for example, the client chooses to create a “custom package” of products A, B, C, D, E, and F. We already have a predefined package containing A, B, and C called Foo. So the order will then be Foo, D, E, and F.

The catch has the least number of individual elements, followed by the least number of packets. 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 just take the greatest match, then I have 1 (5pc) packet and 5 separate elements. No packages (2) and (3) can be built with the rest of the elements.

If I look deeper, I find that without creating a package (1), I can instead create a package (2) and a package (3). This means that I have 2 packages and 4 separate elements (the best choice in this buisiness rule).

Since I use MySQL, I hold back only one level of sub-block selection (as far as I know). So this view should be done in php. I looked at using array_intersect () to match, but every factor found exponentially grows with respect to processing, as the number of predefined packets grows linearly.

I ran this a couple of other coder friends and again, while it seemed like there should be a simple answer, which we all found out that it was not as simple as it seems. So, I thought I'd post it here like a good noodle stretcher. Thanks so much for your time!

Answer 1

The problem is usually “complex” (speaking in terms of computational complexity). In fact, it trails several bells in the back of the head, which probably comes down to one of such classic problems with algorithms as the Knapsack problem , but I can’t attach my own name to it.

However, with such a small problem space (they can only choose 10 products), it should be fast enough to just overdo the thing. When someone sends a custom assembly, just recursively attack it with all the features and see which one is better.

That is, take the components that they have selected, and first try to remove the Package 1 components from it. If possible, take the rest of the components and try to extract the components of "Package 2" from it, etc. Keep track of the best solution you have found so far.

If it is still not fast enough (but I think it will probably be, depending on how many pre-packaged you have), you can apply some dynamic programming to speed it up.

---

Edited to add:

Depending on the number of possibilities and how long it really needs to be done, you can write the code described above, and then simply list all the solutions for each possible combination. Then, when someone sends a custom assembly, you just need to get the answer, and not calculate it from scratch every time.

Even if you don’t want to pre-compute them, I suggest storing the result every time someone creates a custom assembly, and then in the future, if someone else does the same normal assembly that you don’t need to recount the solution.

Answer 2

I suggest you help the client. On the product selection screens, show which packages are available and let them make combinations (evaluated accordingly so that the sum of the amounts is sufficient to cover the special processing).

Answer 3

Sorry I made your problem a little more complicated. :-)

Despite the fact that you may need to pre-calculate possible solutions, or do users really choose from predefined packages: what if the predefined package is no longer in stock?

What if there is currently no solution to complete the order? Then you will send part of the order, and if so: will you add individual items, even if you know that after a while you can select a predefined package?

And are you sure that no preference will be assigned to predefined packages? How and which predefined package to select when ordering "ABCD" and the predefined packages "ABC" and "BCD" exist? If, for example, you know that the predefined “ABC” package is often out of stock, then perhaps this will make “BCD” preferred when possible.

So: perhaps you need to use some modeling in which you can easily change some hard-coded rules, rather than trying to find an automatic solution. Of course, it could be PHP itself.