Finding the Best Top Up Plans for Mobile Prepaid Users by Knapsack Algorithm

Original Idea

Just Imagine that you are a thief.....and you are out to rob a house with a knapsack which has the following items :- 10 kg of ITEM1 giving 35 units of profit, 25 kg of ITEM2 giving 40 units of profit, 20 kg of ITEM3 giving 30 units of profit.(each ordered from Most expensive to lesser expensive), but your knapsack can only carry/hold 40 kgs.

(* THINK OF THESE ITEMS AS SMALL ITEMS WHICH CAN BE TAKEN BY PART OR AS A WHOLE)

Below is the tabular format :-

Item	Profit	Weight
1	35	10
2	40	25
3	30	20

So what do you do  such that you get the most profit ?

You have to rob in such a way that you get the max profit from the least weight.

How do you know which item will give me more profit ?

You take the ratio of profit by weight, and select the items based on higher ratio to lower ratio.

So that gives:-

Item	Profit	Weight	Ratio(P/W)
1	35	10	3.5
2	40	25	1.6
3	30	20	1.5

Now the calculation comes :-

Initial values
Profit(P) = 0, Weight(W)=40

Step 1:-

P = 0+35=35
W=40-10=30

Step 2:-

P = 35 + 40 = 75
W = 30-25=5
*You can stop calculation here if you do not want the profit to be earned in parts(i.e. stop calculation if your items cannot be broken into smaller quantities)

Step 2:-

P = 75 + (30/20)*5=82.5
W = 5-5=0

So totally you get 82.5 units of profit for exact 40 kg of weight.

--------------------------------------------------------xxxxxxxxxx---------------------------------------------------
Applied idea :- 

Think that you have a budget of 150 Rs. (approx. 2.262$) (Weight of knapsack) and you want to recharge in such a way that you get the most of that 150 Rs.

Now refer to this table of a network provider's

Item	Wieght(price)	Profit(value it gives)
1	10Rs.	7.73Rs.
2	18Rs.	18Rs.
3	20Rs.	15.47Rs.
4	30Rs.	23.2Rs.
5	47Rs.	47Rs.
6	50Rs.	40.67Rs.
7	60Rs.	49.4Rs.
8	70Rs.	58.14Rs.
9	90Rs.	75.6Rs.
10	100Rs.	84.34Rs.

Now a normal person if he wants to recharge for 150 Rs. would usually recharge for a 50 Rs. then 100Rs. See the table below

Item	Weight(price)	Profit
1	50	40
2	100	84
Result	150 Rs.	124 Rs.

So you will get 124 Rs. Talktime for 150 Rs. spent.

Now apply the algorithm.....and see the result

Item	Weight(price)	Profit
1	47	47
2	100	84
Result	147 Rs.	131 Rs.

So you will get 131 Rs out of your 147 Rs. (3 Rs. saved and 7 Rs. more talktime can be used).

This was just a very small demo of what this algorithm can do for this current situation. This was just one of the examples....In India there are about 1.25 billion people as of 2013, and according to this research 95% of peolpe are using pre-paid plans.

There are around 7 major telecom operators which gives around close to ~250 different pre-paid plans.

So if this algorithm is applied to an app which calculates best plan for a user according to his/her budget there can be better use of talktime for their money.

Here is the link of the app i have made.

Here is the C algorithm(Just algorithm, not much functionality).Link

Knapsack Algorithm wiki page