Discount Knapsack Dynamic Programming Optimization – Ordering

Dynamic programming for discount knapsack problem requires pre-ordering of the basic discount applications. For our discussion, we assume we have enabled pruning for dynamic programming.

It’s natural to order by per unit value descending, so it would get the best deal faster and so pruning would become more effective.

If we look at our discount concurrency closer, often times discounts overlap with each other over a small set of products. So it makes sense to give overlapped products more weight in ordering. One option is to order by per unit value over overlapped products, descending.

Which one works better? Experiment shows that it’s mostly a tie – one works better in some cases, while the other one in other cases. By examining the experiment data closely, it turns out if number of basic discount applications is small, say less than 10, then focusing on overlapped products works better in general; otherwise, straightforward ordering better.

How about a mixed approach? It seems to work for me, but you have to work out your own experiment to fine-tune for yourself.

Related: Dynamic Programming for Retail Discount Knapsack Problem