Discount Knapsack Dynamic Programming Optimization – Pruning

Update - this blog post has been moved to Dynamics 365 Community. Earlier, we introduced dynamic programming algorithm for retail discount concurrency problem, which for most part is a multi-dimensional integer knapsack problem.

Today, we’re adding pruning technique to speed up the algorithm. For the record, pruning isn’t specific to dynamic programming. In fact, pruning is an essential part of another algorithm: branch and bound.

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.

Let’s refresh ourselves how dynamics programming works for zero-one knapsack problem.

As we discussed before, unbounded integer knapsack problem can be turned into a zero-one knapsack problem, and as such, we focus on zero-one knapsack problem.

1. Items (basic discount applications) are ordered in some ways.
2. Solve the problem by breaking up the problem into smaller pieces recursively from top down:

DP(i, w) = max(DP(i–1, w-w_i) + w_i, DP(i–1, w))

where DP(i, w) denotes the best deal for weight w, taking into account first i basic discount application, where 1 <= i <= n.

How pruning works.

1. Establish a baseline deal or current best deal first – if we get a better deal later, we will update the baseline deal.
2. At any given point, say DP(i, w), we estimate the potential with weight w and remaining basic discount applications: i, i+1, …, n, and add the realized values we’ve already got. If the total (realized + potential) is less than the current best deal, we stop going down recursively.

Example:

The following is a list of items you can pick for your knapsack with weight 8. You can take at most one each. We've also constructed 2 additional columns: "unit price" and "best unit value from bottom up" for pruning.

Item	Value	weight	Unit value	Best unit value from bottom up
A	$8	5	$1.6	$2=max(1.6, 2)
B	$6	3	$2	$2=max(2, 1,5)
C	$3	2	$1.5	$1.5=max(1.5,1.5)
D	$9	6	$1.5	$1.5

 

1. We order items in some way. For our exercise, we assume the order as in the table.
2. We build a list of best unit values from bottom up, as in column 5 above.
3. Dynamic programming with pruning
   1. Take “A” with realized value $8, and move onto next item with remaining weight 3.
      1. Take “B” with value $6. There is no more weight left, we get baseline deal of $14.
      2. Not take “B”, and move onto next item with remaining weight 3. The potential is 3 * 1.5 = $4.5. Add realized value of $8, and the best you can is $12.5, which is worse than the current best deal. So we prune the path down.
   2. Not take “A” , and move onto next item with remaining weight 8. I’ll leave the rest as an exercise, if you’re interested.

Now, build your own pruning in the sample code.

Related: Retail Discount Concurrency – Best Deal Knapsack Problem

Related: Dynamic Programming for Retail Discount Knapsack Problem