I have been wondering about this issue for quiet some time now. I find interesting and I have not been able to come up with a solution.

This must be seen in a context of a shopping cart where you can first choose to add 1 gold bar to your cart and then add another 2, so the sum is 3.

Let's say we have these products:

1 gold bar = 40$ 2 gold bars = 80$ 3 gold bars = 110$

So when I add 1 gold bar, my cart is 40$ dollars worth. Adding another 2, then my cart is 120$ worth.

Now I have 3 gold bars in my cart.

But there is a price for 3 gold bars at 110$, and I want that price to kick in of course, because I do have 3 gold bars in my cart.

Can this be categorized as a normal knapsack issue ? Or are there any other way of looking at it ?

Thank you


I agree it sounds like dynamic programming. BTW the question phrasing doesn't say how you wanted to approach some edge cases, e.g.

  1. There could be a few combinations of deals to "cover" the shopping cart, e.g. if the cart has 6 bars, and you have a special discount for a bulk of 3, and a different discount for bulk of 4, you should see what's cheaper: two deals of 3 (6=3+3) or one deal of 4 while the remaining 2 are without discount (6=4+2).
  2. Sometimes, buying *more* ends up cheaper or the same, and as a customer I saw humans/sites that would note "hey, you might as well get another one, it'll be cheaper".

I saw this discussion: https://stackoverflow.com/questions/3495916/minimize-price-for-volume-discount-orders
(also there is a more generalised problem of "internet shopping problem", but I think it's an overkill if you're really just running one site which has a small number of deals).

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.