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

Comments (0)

Skip to main content