edited by
2,527 views
13 votes
13 votes
Consider the following problem. Given $n$ positive integers $a_{1}, a_{2}\dots a_n,$ it is required to partition them in to two parts $A$ and $B$ such that, $\displaystyle{}\left|\sum_{i \in A} a_{i} - \sum_{i \in B} a_{i}\right|$ is minimised

Consider a greedy algorithm for solving this problem. The numbers are ordered so that $a_{1} \geq a_{2} \geq \dots a_{n},$ and at $i^{th}$ step, $a_i$ is placed in that part whose sum in smaller at that step. Give an example with $n=5$ for which the solution produced by the greedy algorithm is not optimal.
edited by

2 Answers

16 votes
16 votes

Let $S = \{12,11,8,8,8\}$

As per the given greedy algorithm we get $A = \{12,8 \}$ and $B = \{11,8,8\}$ and $|\sum_{i \in A} a_{i} - \sum_{i \in B} a_{i}| = |20 - 27| = 7.$ 

This is not minimal because if we partition $S$ as $A = \{12,11\}$ and $B = \{8,8,8\}$ we get $|\sum_{i \in A} a_{i} - \sum_{i \in B} a_{i}| = |23 - 24| = 1.$ 

Thus greedy algorithm fails for this example.

Working algorithm: https://www.geeksforgeeks.org/partition-a-set-into-two-subsets-such-that-the-difference-of-subset-sums-is-minimum/ 

2 votes
2 votes

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.

 

  1. 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

 

  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

  1. 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.

edited by

Related questions

11 votes
11 votes
1 answer
1
makhdoom ghaya asked Nov 19, 2016
5,829 views
Match the pairs in the following questions:$$\begin{array}{|ll|ll|}\hline (a) & \text{Strassen's matrix multiplication algorithm} & (p) & \text{Greedy method} \\\hline (...
7 votes
7 votes
1 answer
3
makhdoom ghaya asked Nov 25, 2016
2,381 views
Consider a hash table with chaining scheme for overflow handling:What is the worst-case timing complexity of inserting $n$ elements into such a table?For what type of ins...