Discount Knapsack Dynamic Programming – Bounded I
So far, we have mostly talked about unbounded discount knapsack problem, or unbounded multi-dimensional integer knapsack problem.
Sometimes, retailers want to place a limit. For example, you get 40% of a keyboard, but up to 2. That’s our focus today: mixing in bounded discounts.
On the surface, it seems to make the problem smaller because it’s bounded. However, smaller doesn’t make it simpler. On the contrary, smaller makes it more complicated in many ways. We will focus on dynamic programming. Most of the issues and ideas will be relevant for other algorithms as well.
Quantity control. At every step (dynamic programming state), before we apply a discount application, we need to check whether we can apply one more if the discount application is bounded.
Caching. Also known as memoization in dynamic programming. Caching would become less efficient and mostly invalid, but still possible.
- Unconditional sub-deal. None of the discount applications considered for the sub-deal can be bounded
- Conditional sub-deal that may be used for pruning. Some of the discount applications considered for sub-deal are bounded, while it is still the best deal, assuming it’s not restricted by what has been applied before. In practice, the benefit is questionable.
In many cases, especially with many bounded discount applications, the cost of maintaining the cache is too high for the benefit. In some cases, it may still help. For example, we don’t have many bounded discount applications, and they’re mostly at the beginning of the ordered list for dynamic programming.
Purging. We can still use unbounded discount applications to purge bounded discount applications, but not the other way around. Again more complexity.
Pruning. It doesn’t have much effect. In fact, we could make it more efficient if we apply more aggressive potential calculation. Please be aware that more aggressive potential calculation doesn’t always mean better performance.
Compounded. If you have read my previous posts on compounding, I hope you got the impression that mixing in compounding would make a problem more complicated, sometimes much more. And as always, compounding would have its own post.
Related: Dynamic Programming for Retail Discount Knapsack Problem
Related: Discount Knapsack Dynamic Programming Optimization – Pruning
Related: Discount Knapsack Dynamic Programming Optimization – Purging I