Discount Best Deal Algorithm – Mixing in Compounded Discounts II
In the first post, we mentioned that compounding may invalidate dynamic programming, actually, any algorithm for discount knapsack problem. We also discussed about converting knapsack problem that involves compounded discounts into one that doesn’t.
In this post, we will discuss the cases where we really have to deal with compounding in the dynamic programming algorithm.
Warning: the more and deeper you think, the more it spins your brain. If you think it's too much - it is - avoid it at all cost.
- Memorization or caching won’t be valid anymore, because the value of a compounded discount application depends on what has been applied before it.
- Dynamic programming relies on pre-ordering of discount applications. In general, for compounded discounts, not discount applications, we prefer a fixed order of how to apply them, i.e. say, we have 2 discounts, mix and match and simple, covering many products. We don’t want apply mix and match first then simple in some cases, while in the reverse order in other cases. Here’s one option,
- Consider all compounded discounts as a block, whose discount applications will appear either before all non-compounded ones, or after. If before, we can still leverage memorization for the bottom half of non-compounded discount applications.
- Order compounded discounts in some way, and for each, line up its discount applications.
- Pruning depends on potential calculation for the remaining products with the remaining discount applications. Potential calculation will need to take compounding into account, which is not trivial, but possible. As you can expect, pruning will become less efficient.
- At each step (or dynamic programming state), we have to keep track of what compounded discount application have been applied. In addition, we have to figure out what are the remaining quantities for a specific compounded discount. Put it in a different way, when applying a non-compounded discount, we just reduce the quantities for the rest. However, when applying a compounded one, we need to reduce the quantities for all non-compounded discounts, and for itself, but not for other compounded discounts.
- It’s no simple task to figure out the actual value of a compounded discount, given already applied discount applications. Take a simple example with 2 keyboards: apply buy one get one for 1 cent first, and then a simple $5 off. The complex grows as we increase product quantities and/or mix in more products.
All in all, it would make dynamic programming much more complex, and much less efficient.
Lastly, what about other algorithms, for example, branch and bound? In general, dynamic programming performs better than branch and bound because of memorization. Dealing with compounded discounts, dynamic programming loses its advantages. Regardless, both have to deal with huge complexity introduced by compounding.
Related: Discount Best Deal Algorithm – Mixing in Compounded Discounts I
Related: Dynamic Programming for Retail Discount Knapsack Problem