How can I efficiently find the optimal order to apply special offers to a shopping cart? 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?
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.