Dynamic Programming for Retail Discount Knapsack Problem
Update - this blog post has been moved to Dynamics 365 Community.
Earlier, we explained that retail discount best deal problem is a multi-dimensional integer knapsack problem.
Today, we apply dynamic programming.
From wikipedia, dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler sub-problems, solving each of those sub-problems just once, and storing their solutions – ideally, using a memory-based data structure.
In our one-dimensional case, assuming we have n items, each weighing wi. Let DP(i, w) be the best deal for weight w, taking into account first i items, where 1 <= i <= n. We have,
DP(i, w) = max(DP(i–1, w-wi) + wi, DP(i–1, w))
The calculation is essentially to fill up best deal matric of n*w, where n is the number of items and w the knapsack size/weight, and the value of each cell is DP(i, w).
Dynamic programming for zero-one knapsack problem is beyond trivial.
If you’re serious about dynamic programming, I’d encourage you not look at my sample code, and just program your own code.
Two flavors of dynamic programming, bottom up or top down.
The complexity is O(n*w) and memory usage is at most O(n*w). If you try a real example, with top-down approach, you’ll see it’s a sparse matrix.
In general, for one specific knapsack, top down is more efficient as it fills up fewer cells in the calculation matrix.
In the sample code, all is top down, except dynamic programming with list, which is bottom up.
Turn an unbounded integer knapsack problem into a zero-one knapsack problem.
I learned the trick from a colleague. In short, we can apply binary transformation to turn an unbounded integer knapsack problem into a zero-one knapsack problem. As an example, say we have 2 items. For unbounded knapsack problem, you can fill as many of them as you want, limited by the knapsack size/weight.
| Item (unbounded) | Value | Weight |
| A | $3.5 | 3 |
| B | $2.5 | 2 |
For a given knapsack size/weight, say 9, this is equivalent to a zero-one knapsack problem with items
| Item (zero-one) | Value | Weight |
| Ax1 | $3.5 | 3 |
| Ax2 | $7 | 6 |
| Bx1 | $2.5 | 2 |
| Bx2 | $5 | 4 |
| Bx4 | $7.5 | 8 |
The logic for multi-dimension knapsack problem is essentially the same.
The main variation is to ensure an item fits into remaining weight for all dimensions.
For now, it’s all theory. What about retail discount in practice? Until next time.
Related: Retail Discount Concurrency – Best Deal Knapsack Problem Sample code