Ask Learn
Preview
Please sign in to use this experience.
Sign inThis browser is no longer supported.
Upgrade to Microsoft Edge to take advantage of the latest features, security updates, and technical support.
Note
Access to this page requires authorization. You can try signing in or changing directories.
Access to this page requires authorization. You can try changing directories.
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.
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
Please sign in to use this experience.
Sign in