Discount Knapsack Dynamic Programming Optimization – Purging I
Prerequisite: please make sure you’re familiar with the basics of the dynamic programming. Either you’ve programmed your own zero-one knapsack problem, or you have debugged the sample code.
We know that retail discount best deal problem is mostly a multi-dimensional integer knapsack problem, where we structure the best deal from a pool of basic discount applications. Let’s take a look at the pool before we apply any algorithm.
First, a simple zero-one knapsack case. Obviously, in the following example, you’d never grab B, because C has the better value of the same weight. In other words, C dominates B and we can remove B from the pool.
| Item | Value | weight |
| A | $8 | 5 |
| B | $2 | 2 |
| C | $3 | 2 |
We can apply the same purging principle with our multi-dimensional integer knapsack problem. Multi-dimensional only makes it a bit more complex.
Multi-dimensional knapsack case. Let’s bring back our original case.
- Two products, keyboard costing $20, and mouse $10.
- A simple discount of 40% for both.
- Buy one get (least expensive) one free for both.
We’d have multiple basic discount applications. For B1G1 with 1 keyboard and 1 mouse of $10, we can always replace it with a simple discount of both products, of $12. In other words, we can remove B1G1 with 1 keyboard and 1 mouse, because it’s dominated by others.
| Id | Basic discount application |
| S1 | Simple discount for 1 keyboard of $8 |
| S2 | Simple discount for 1 mouse of $4 |
| MM11 | B1G1 for 2 keyboards of $20 |
| MM22 | B1G1 for 2 mouse of $10 |
| MM12 | B1G1 for 1 keyboard and 1 mouse of $10 |
In addition, let’s move onto unbounded discount knapsack problem. We’ve mentioned before that we can turn the unbounded integer problem into a zero-one problem. In essence, we perform the binary transformation of basic discount applications, and the pool is now filled with a list of binary multiples. For example, for basic discount application S1 above, we’d have basic binary multiples: S1x1, S1x2, S1x4, S1x8, up to the knapsack weight (product quantities in the transaction).
Now let’s compare S1x2 and MM11x1: both takes 2 keyboards. MM11x1 gives the better value of $20, so we can remove S1x2 (and all the multiples up: S1x4, S1x8, etc.)
We can also purge basic binary multiples, in the same spirit.
How do we purge then? Hint: we don’t have look beyond what we have discussed. Until next time.
Related: Dynamic Programming for Retail Discount Knapsack Problem