Discount Knapsack Dynamic Programming Optimization – Purging II

  • Article

We knew we could we simplify the discount knapsack problem by purging. Now, let’s get to technical details of implementation with a focus on unbounded discount knapsack problem: Given a list of basic discount applications, how to purge dominated ones from the list.

Whether we can purge a basic discount application is equivalent to whether we can construct a better deal using other basic discount applications. It’s essentially what dynamic programming is trying to solve. The purging algorithm with dynamic programming is a lot simpler than the one to construct the best deal because of a couple of subtle differences.

We only need to find out whether there exists a better deal. In other words, we don’t have to know the details of the deal, so we don’t have to keep track of the details (basic discount application combinations) along the way. In addition,

We are done as soon as we find out the basic discount application can be bettered. In other words, we don’t have to find the best deal, given product quantities in the basic discount application to purge.

Let’s move on to the overall algorithm for the purging problem: Given a list of basic discount applications, how to purge dominated ones from the list. Recall the first step for dynamic programming is to order the basic discount applications. Since we will check if we can purge every single basic discount application from the list, it would be nice to avoiding ordering for every single basic discount application in the list.

Preparation: class ProductQuantitiesKey (for each basic discount application) that is basically a dictionary of required product (index) to required quantity.

  1. Implement equals and hash: the dictionary has to be the same.
  2. Property: TotalQuantity

Build a sorted lookup (dictionary) from TotalQuantity to lookup of ProductQuantitiesKey to the basic discount application BaseDiscountApplication from the original list. If two discount applications share the same ProductQuantitiesKey, the better one wins automatically.

Initialize an empty list of basic discount applications (BaseDiscountApplication): listToKeep.

Purge basic discount applications as follows, by looping through the lookup built earlier, in the increasing order of TotalQuantity.

  1. If listToKeep is empty, add to listToKeep all basic discount applications in lookup of ProductQuantitiesKey to BaseDiscountApplication, and continue the loop.
  2. Initialize an empty list of basic discount applications (BaseDiscountApplication): listToKeepInLoop.
  3. Order basic discount applications in listToKeep for dynamic programming.
  4. For each pair in lookup of ProductQuantitiesKey to BaseDiscountApplication, check if we can purge using dynamic programming. If not, add it to listToKeepInLoop.
  5. Add listToKeepInLoop to listToKeep.

Notes:

  1. During the dynamic programming evaluation, we need to skip the very base discount application we’re trying to purge in the ordered list.
  2. We can purge for basic binary multiples as well in the same spirit.
  3. We ignore discount applications with partial quantities in the purging with dynamic programming.
  4. If we need to take into account bounded discount applications, then we can’t use them to purge others, but we can still use the unbounded discount applications to purge all.

Related: Discount Knapsack Dynamic Programming Optimization – Purging I