5 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

$|\sum_{i \in A} a_{i} - \sum_{i \in B} a_{i}|$ 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.

$|\sum_{i \in A} a_{i} - \sum_{i \in B} a_{i}|$ 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.

6 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/

0

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

at $i^{th}$ step, $a_i$ is placed in that part whose sum in smaller at that step.

This is what is means by the above-quoted line$?$

$12\Rightarrow set_1,$ $set_1=\{12\}$

$11\Rightarrow set_2,$ $set_2=\{11\}$

$8\Rightarrow set_2,$ $set_2=\{11,8\}$

$8\Rightarrow set_1,$ $set_1=\{12,8\}$

$8\Rightarrow set_2,$ $set_2=\{11,8,8\}$

$set_1=\{12,8\}$ $set_2=\{11,8,8\}$