How to build the Greedy Algorithm ?
we have $a_1,a_2,…,a_n$ in set S.
Every element should belongs to either A or B but not both. So, our solution will have $’n’$ steps where in each step, we’ll place one element into either A or B.
Given that, at step i, $a_i$ chosen,
that means, on step 1, $a_1$ will be placed to either A or B, on step 2, $a_2$ will be placed to either A or B etc
Algorithm like :
put $a_1$ into A
for i=2 to n
add $a_i$ in A if Adding it in A makes |(Sum of elements of A + $a_i$) – Sum of elements of B| smaller than |Sum of elements of A – ( Sum of elements of B + $a_i$ )|, else add it in B.
- let S = {18, 10,10,5, 2}, Our greedy algorithm work like :
step 1 : add $a_1=18$ into A. ==> A={18}, B= ∅ :: sum difference = 18
step 2 : add $a_2=10$ into B. ==> A={18}, B={10} :: sum difference = 8
step 3 : add $a_3=10$ into B. ==> A={18}, B={10,10} :: sum difference = 2
step 4 : add $a_4=5$ into B. ==> A={18,5}, B={10,10} :: sum difference = 3
step 5 : add $a_5=2$ into B. ==> A={18,5}, B={10,10,2} :: sum difference = 1
- let S = {30, 10,10,5, 2} Our greedy algorithm work like :
step 1 : add $a_1=30$ into A. ==> A={30}, B= ∅ :: sum difference = 30
step 2 : add $a_2=10$ into B. ==> A={30}, B={10} :: sum difference = 20
step 3 : add $a_3=10$ into B. ==> A={30}, B={10,10} :: sum difference = 10
step 4 : add $a_4=5$ into B. ==> A={30}, B={10,10,5} :: sum difference = 5
step 5 : add $a_5=2$ into B. ==> A={30}, B={10,10,5,2} :: sum difference = 3
But if you observe this, first element goes to A then second element should be goes to B
what if i encounter a sequence where $a_1+a_2$ equal to rest of the elements ? then surely our greedy algorithm fails
- let S = {15, 15,10,10, 10}, Our greedy algorithm work like :
step 1 : add $a_1=15$ into A. ==> A={15}, B= ∅ :: sum difference = 15
step 2 : add $a_2=15$ into B. ==> A={15}, B={15} :: sum difference = 0
step 3 : add $a_3=10$ into B. ==> A={15,10}, B={15} :: sum difference = 10
step 4 : add $a_4=10$ into B. ==> A={15,10}, B={15,10} :: sum difference = 0
step 5 : add $a_5=10$ into B. ==> A={15,10,10}, B={15,10} :: sum difference = 10
But we have A={15,15}, B={10,10,10} which is optimal.