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