Tags

We all love algorithms. In real life, the problems do not pose themselves as textbooks problems under a particular chapter so that we know what algorithm to apply. The problems are camouflaged. The challenge lies not in implementing the algorithms but identifying the problem in its abstract form and finding out the appropriate algorithm to apply.

I have had a few chances at my work where I’ve had this Aha! feeling along with my colleagues where we talked about the problem, reformulated it and then discovered that the problem is a likely candidate for applying some algorithm X. This is the first part of this series.

To boost the sales of our product, we had come up with certain promotions. Some were simple flat rate discount, some were % discounts. Then we embarked on this idea of buy-one-and-get-one-free. Here the user chooses products of different prices and pays for approximately half the price. It is similar to buy-one-shirt-and-get-one-free (where you pay for the costlier one). Just that here it is bundle of products.

Let me explain with an example.
1. Suppose a customer buys products each worth \$10, \$30 & \$100. Then the customer would pay \$100 and get \$40 (=10 +30) worth products free. So this ain’t a simple buy-one-get-one free.
2. If customer buys two products each worth \$100, then she pays \$100 and gets the other one free.
3. If the purchases are \$10, \$100, \$45, \$40, \$10 then customer pays \$105 (= 10+45+40+10) and gets the \$00 product free.
This should give a fair idea of what we want to achieve. A little thought would suggest such a reformulation of the problem above.

“Given a set of numbers, split it into two parts such that the difference between their sums is the least.”

This is quite straight forward to solve. The plan is given below.
1. sort the numbers in descending order.
2. have two buckets call them L & R.
3. put the first one into L (l1). put the second one into R (r1).
4. take the third one x3.
if r1+x3 > l1 then put x3 in L1
else put x3 in L2

Now it is a matter of policy whether the customer is charged the higher one or the lower (in cases where the split is unequal)

If you like this you might probably like this as well.