title: e-commerce: Algorithm for calculating discounts
body: <p>I'm in need of expert advice on a tricky matter.</p>
  
  <p>The scenario is:</p>
  
  <ul>
  <li>e-commerce web-site</li>
  <li>lots of products</li>
  <li>lots of discounts mixed on these products</li>
  </ul>
  
  <p>A product is identified by a unique ProductID and has a sales price. Very classic scenario.
  The product can also be in one or more discounts.</p>
  
  <p>A discount can be of different types. One example of a discount is:</p>
  
  <ul>
  <li>Buy two or more within a set of products and get X percent off each product</li>
  </ul>
  
  <p>A line item can only get one discount thus once a line item has been discounted it is not available for other discounts.</p>
  
  <h2>Test Case Data:</h2>
  
  <ul>
  <li>Product-1: $10</li>
  <li>Product-2: $10</li>
  <li>Product-3: $50</li>
  <li>Product-4: $100</li>
  </ul>
  
  <p><strong>Discount-A</strong>: Buy two or more and get 20 % off the any of the following products</p>
  
  <ul>
  <li>Product-1 </li>
  <li>Product-2 </li>
  <li>Product-3</li>
  <li>Product-4</li>
  </ul>
  
  <p><strong>Discount-B</strong>: Buy product and get 50 % off the following product</p>
  
  <ul>
  <li>Product-3 </li>
  </ul>
  
  <h2>Test Scenario 1:</h2>
  
  <p><strong>Basket</strong>: containing line items with:</p>
  
  <ul>
  <li>Product-1</li>
  <li>Product-3</li>
  <li>Product-4</li>
  </ul>
  
  <p><strong>Calculation #1</strong>: </p>
  
  <ul>
  <li>Discount-A: Product-1, Product-3, Product-4 = $2 + $10 + $20 = $32
  <ul>
  <li>= $32 total saving</li>
  </ul></li>
  </ul>
  
  <p><strong>Calculation #2</strong>: </p>
  
  <ul>
  <li>Discount-A: Product-2, Product-4 = $2 + $20 = $22</li>
  <li>Discount-B: Product-3 = $25
  <ul>
  <li>= $22 + $25 = $47 total saving</li>
  </ul></li>
  </ul>
  
  <p>Which means that a combination of <strong>Discount-A</strong> and <strong>Discount-B</strong> will give the best possible discount for the customer.</p>
  
  <h2>Test Scenario 2:</h2>
  
  <p><strong>Basket</strong>: containing line items with:</p>
  
  <ul>
  <li>Product-3</li>
  <li>Product-4</li>
  </ul>
  
  <p><strong>Calculation #1</strong>: </p>
  
  <ul>
  <li>Discount-A: Product-3, Product-4 = $10 + $20 = $30
  <ul>
  <li>= $30 total saving</li>
  </ul></li>
  </ul>
  
  <p><strong>Calculation #2</strong>: </p>
  
  <ul>
  <li>Discount-B: Product-3 = $25
  <ul>
  <li>= $25 total saving</li>
  </ul></li>
  </ul>
  
  <p>Which means that applying <strong>Discount-A</strong> will give the best possible discount for the customer.</p>
  
  <hr>
  
  <p>In order to calculate the best discount for a given basket, literally all combinations of products and available discounts on these products must be evaluated.</p>
  
  <p>Normally there is 30-40 line items in a basket each with 0-3 discounts each.</p>
  
  <p>Basically I'm stuck with finding an efficient way to do this calculation. </p>
  
  <p>Right now the algorithm I have for applying the discounts is something like:</p>
  
  <ul>
  <li>Clear discounts on the Basket</li>
  <li>Get all unique ProductID's for LineItems in the Basket</li>
  <li>Get all discounts available for these ProductID's</li>
  <li>For-Each Discount (unordered)
  <ul>
  <li>Apply the Discount if it is satisfied by non-discount flagged line items
  <ul>
  <li>Flag line items in discount as discounted</li>
  </ul></li>
  </ul></li>
  </ul>
  
  <p>But this is not at all sufficient as it does not try out different combinations of line items / discounts.</p>
  
  <p>I've been searching around for standardized algorithms that can solve problems like this, but without any luck so far.</p>
  
  <p>Hope to hear from you :)</p>