Ask Learn
Preview
Ask Learn is an AI assistant that can answer questions, clarify concepts, and define terms using trusted Microsoft documentation.
Please sign in to use Ask Learn.
Sign inThis browser is no longer supported.
Upgrade to Microsoft Edge to take advantage of the latest features, security updates, and technical support.
Note
Access to this page requires authorization. You can try signing in or changing directories.
Access to this page requires authorization. You can try changing directories.
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.
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
Ask Learn is an AI assistant that can answer questions, clarify concepts, and define terms using trusted Microsoft documentation.
Please sign in to use Ask Learn.
Sign in