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.
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.