5
$\begingroup$

Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the order to apply the special offers to minimize the final basket price?

For example, I have in my cart 4 items:

  • Coke \$2
  • Coke \$2
  • Sandwich \$3
  • Chocolate bar \$1

Total: \$8

There are two special offers in store:

  • Buy one get one free coke (\$2 saving).
  • Coke, chocolate bar and a sandwich for \$4.50 (\$1.50 saving).

One method of determining the order offers are applied might be to sort them by the savings they give. After applying the offers using this method my cart now looks like this:

  • Buy one get one free coke \$2
  • Sandwich \$3
  • Chocolate bar \$1

Total: \$6

There is no meal deal offer applied because after the Coke deal is applied there is not any coke items left to make a meal deal. This method of sorting by savings may seem to work, but there are cases in which it can fail, for example if the same deals were in place and my cart looked like this:

  • Coke \$2
  • Sandwich \$3
  • Chocolate bar \$1
  • Coke \$2
  • Sandwich \$3
  • Chocolate bar \$1

Total: \$12

After deals are applied, the two Coke items are substituted for the promotional offer first (it being the deal with the greatest saving). There is no other applicable deal so the algorithm ends, reducing the basket price by \$2. Obviously there is an error here because if two meal deals were applied before the coke deal, the price would have been reduced by $3.

The naive solution to this problem would be to enumerate each possible permutation of the list of special offers, and find the one that minimizes the basket total when applied. This would have a factorial runtime based on the number of special offers available.

Is it possible to improve on a factorial runtime and if not, are there any efficient approximate solutions?

$\endgroup$
  • 2
    $\begingroup$ Whenever you have a factorial runtime in a problem that requires finding an optimal ordering, you should look towards the Held-Karp approach for TSP. $\endgroup$ – Tom van der Zanden Jun 28 '15 at 20:09
  • $\begingroup$ Dynamic programming looks applicable. $\endgroup$ – vonbrand Feb 24 '16 at 17:43
1
$\begingroup$

Interesting problem. As noted, you can easily turn this into an integer programming problem. But if your numbers are small and nobody buys a warehouse full of goods an easy algorithm may work.

All you need to decide is how often each offer is applied. Sort the offers by percentage saved in descending order. Then an outer loop where the most saving offer is applied first as often as possible first descending. Then the second highest percentage saving etc. You reject a search path if it cannot be optimal.

In your example the first offer saves 50% and the second just 25%, so you would apply the first offer as often as possible,

It gets a bit more complicated if you accept offers where you deliver more than ordered. For example delivering an extra chocolate bar if it saves money

In your second example you would first try to apply the first deal once, then try again without it.

$\endgroup$
  • $\begingroup$ Indeed: an inefficient algorithm may actually work quite well enough; and, more important, can be made so simple that its correctness is obvious to anyone. It depends on the number of offers; but even if there are 10 of them, $10!$ is only about 3 million. $\endgroup$ – Martin Kochanski Jun 23 '16 at 19:09
0
$\begingroup$

First, note that order does not matter. If it is possible to apply both offer 1 and offer 2, then it doesn't matter which order you apply them in: the result will be the same either way.

Probably the most pragmatic solution will be to use integer linear programming. Introduce a variable $x_i$ to represent the number of times you apply offer $i$. Also, for each product $j$ in your initial order, have a variable $y_j$ to represent the number of additional orders of project $j$ that are needed after you apply all the offers. You want to minimize $\sum_i c_i x_i + \sum_j c'_j y_j$, where $c_i$ is the price for offer $i$ and $c'_j$ is the price for product $j$. You have some linear equations, one for each product (to ensure that the total quantity of the final order matches the desired number), as well as the inequalities $x_i \ge 0$, $y_j \ge 0$. Now use an off-the-shelf integer linear programming (ILP) solver to find the best solution to that ILP instance.

ILP solvers implement a number of heuristics and techniques that are often effective at reducing the cost of finding a solution. Using an existing ILP solver will take a lot less time than trying to implement a custom algorithm just for your specific situation. And, if the number of products in your shopping cart is not too large, this approach might be efficient enough for practical purposes.

$\endgroup$

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.