Discount Knapsack Dynamic Programming – Adjust for Two Remaining Quantities
As we examined in mixing in exclusive discounts in the concurrency mode of compete within priority and compound across, we may have to deal with uneven knapsack sizes (a.k.a. remaining quantities in Dynamics Retail discount engine) in a knapsack algorithm for discount best deal. We will focus on dynamics programming for now.
I will use the languages in Dynamics Retail discount engine: we have two remaining quantities, one for exclusive discounts and one for compoundable ones.
We need to maintain two remaining quantities in every dynamics programming state (or step): for-exclusive and for-compound. When checking applicability for exclusive discounts, we use for-exclusive quantities; and for compoundable, for-compound ones.
Optimization – Purge: in this specific case, for-compound quantities are always greater than or equal to for-exclusive ones. As such, we cannot use exclusive discounts to purge compoundable discounts if the two (remaining) quantities are not the same. We can still use compoundable discounts to purge exclusive discounts.
Optimization – Caching: Caching would be very complicated and much less effective, even if we can make it work. Recall that the cache key is the index of the discount application multiple and remaining quantities. Now we have two remaining quantities. It’s likely we have to disable it.
Optimization – Pruning: Pruning would be less effective, as we have to assume the larger of the two remaining quantities.
For the record, Dynamics Retail discount engine does not support this at the time of writing. To address the problem, for the concurrency model of compete within priority and compound across, per priority, we always process exclusive discounts first, and after that compoundable ones.
Note: the issues related to the two remaining quantities are similar to those in bounded discount knapsack problem.
Related: Dynamics Retail Discount Details: Remain Quantities I
Related: Retail Discount Concurrency Control – Compete Within Priority and Compound Across
Related: Dynamic Programming for Retail Discount Knapsack Problem
Related: Discount Knapsack Dynamic Programming Optimization – Pruning