We talked about how to design mix and match with fixed quantity setup earlier. The goal is to find the best deal for the customer.
For least expensive, some retailers prefer a solution that favors retailer. For example, buy one get least expensive one 50% off (B1G1 50%). First, it is still least expensive, so if you have $20 and $30, you would get 50% off of $20. But how you pair them when you have multiple choices makes a difference. Favoring retailer option prefer pairing that would cost least (or less) for the retailer. If you have four products in the cart with values: $20, $30, $70 and $80, you would get 50% off of $20 (paired with $80) and $30 (paired with $70), while in best deal case, 50% off of $20 (paired with $30) and $70 (paired with $80).
How to fit favor-retailer least expensive into a best deal knapsack problem?
It is an oxymoron problem: you want to give best deal, but not for least expensive.
Anyway, let’s try at least.
Construct basic discount applications that favor retail only?
In this example, we have two basic discount applications: $20 & $80 for one, and $30 & $70 for another. Allow me to add another simple discount 60% off for $20 and $30 products. It is obvious that the simple discounts wins for $20 and $30 products. Now how do you explain to the customer that you do not give least experience for $70 and $80 combination?
I do not see how it could fit in the best deal discount knapsack problem – if you have an idea, please share it – If cannot, then do not.
Evaluate it before (or after) all other discounts
In other words, it does not participate in best deal discount algorithm.
If it is one line group, it is straightforward: match together one by one the highest priced and the lowest priced products by the number of least expensive products in the mix and match definition, until no more.
Multiple line groups
Anecdote first: I wanted first to disallow multiple line groups for least expensive favoring retailer – we can always enable it when a real customer asks for it – but the program manager pushed me to explore it deeper.
Recall first that the main problem is to match highest priced products with lower priced products according to the line group quantity setup.
One option is to find first lower priced products according to the number of least expensive products in mix and match definition from all line groups. After that, for the remaining quantity in each line group, use the highest priced products. We go through this process until no more. It is natural: we humans can understand it, and it is a beauty if you are into algorithm.
But we are not done yet. Take a look at this example: B1G3 20% off from two line groups: keyboards and mice, each requiring quantity two. In this case, number of least expensive products three is greater than quantity required for each line group. Say, you buy four keyboards and four mice with mouse price lower than keyboard price. By our algorithm earlier, we first need to find three lowest price products and we get three mice, but one mix and match application can take only two mice.
What to do when the number of least expensive products is more than the least of line group quantities? I don’t know. Actually, I didn’t bother. Disallow the case where number of least expensive products is more than the least of line group quantities. This time, program manager didn’t push me because it is not a common setup.
Multiple line groups with overlapping product
With some products covering multiple line groups, while it is possible, it would be highly complicated to match highest priced products and lower priced products according to the line group quantity setup. Please note that we do not want to see match-able products un-discounted as in the example earlier. (I would be highly impressed if you can figure out a way.)
It is natural to make it non-overlapping first, if we do not know how to handle overlapping properly. For example, pre-allocate quantities of products covering multiple line groups to each line group, striving for maximal number of discount applications. For those interested, this is a generic combinatorial problem, which I will list in the end. Again, I would impressed if you have a solution with reasonable outcome, reasonable complexity and acceptable speed.
Multiple favor-retailer least expensive discounts
It is probably not in your design, but if you do not or cannot prevent it, it may happen. The easiest way is to order them in some simple way, and apply one after another.
Appendix: open combinatorial problem
- 3 slots: A, B & C. A takes 3 balls for each level, while B 1 and C 2.
- 4 balls: red, green, blue and black
- A takes red and black
- B take red and blue
- C take green and blue
The goal is to maximize the minimal height of A, B and C, given number of balls for each of red, green, blue and black.