Discount Best Deal Algorithm – Mixing in Compounded Discounts I
I love dynamic programming: It’s simple and fast for retail discount best deal problem.
There is a hidden assumption though: the value of each basic discount application is fixed, regardless of how it mixes with other discount applications. It’s true for non-compounded discounts.
Unfortunately, it’s not true for compounded discounts. Say, you have a compounded 10% off. If you apply it alone, you get 10%, but if you apply it after another discount of 20% off, you’d get 8% off effectively.
The good news is that in some retail cases, we can convert it into non-compounded discount knapsack problem. In fact, in reality it’s a rare case if it doesn’t fall into one of the following two cases.
1. Each product has at most one compounded discount. We can simply treat every compounded discount as non-compounded one.
2. Some products have 2+ compounded discounts. However, each product has at most one multi-item compounded discount. It may have one or more simple discounts.
a. For products with two or more simple discounts only, compound them together for quantity 1 as one composite discount application.
b. For products with one multi-item discounts, construct 2 types of basic composite discount applications.
i. Multi-item discount application compounded with simple discounts, per multi-item discount application quantities, as a new composite discount application.
ii. Per product in the multi-item discount application, compounded simple discounts for quantity 1 as composite discount application. If number of simple discount is one, then just the basic discount application.
As I mentioned in an early post, on the functional side, we should really disable multiple compounded multi-item discounts. For example, make them compete, instead of compounding on top of each other when it happens.
Hopefully, we can stop here.
What if we can’t. It’s too much complexity both on the functional side and on the technical side. We need some coffee. Let’s leave it in another post.
Related: Dynamic Programming for Retail Discount Knapsack Problem