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