We have not talked about threshold discount so far. In fact, my hidden assumption is to evaluate threshold discounts at the very end, after non-threshold discounts: simple discounts, quantity discounts and mix and match discounts – in other words, leaving threshold discounts out of discount knapsack problem – because that’s the nature of threshold discounts and it’s a common practice, and technically because mixing threshold and non-threshold discounts in the discount knapsack problem would be a computation nightmare.
Now there is no reason why you cannot mix them, but you have to be aware of computation cost. Let’s see what happens if we add threshold discounts into the discount knapsack problem. Recall the first step of discount knapsack problem is to figure out all the basic discount applications: the building blocks of the best deal. Take a cart of 10 products, each of quantity 1. How many basic discount applications can we form for the threshold discount? No need for me to explain further.