# GATE1990-12b

543 views
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.
1
This is the partition problem which is NP-Complete. The greedy algorithm would be selecting the elements in reverse order and in alternating fashion distributing them in a and b. This is an approximation algorithm.

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.

0
Ordered in decreasing order
0
My mistake. You're right!

I'll delete my comment
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\}$

## Related questions

1
1.2k views
Match the pairs in the following questions: ...
Express $T(n)$ in terms of the harmonic number $H_{n}= \sum_{t=1}^{n} 1/i, n \geq 1$, where $T(n)$ satisfies the recurrence relation, $T(n)=\frac{n+1}{n} T(n - 1)+1$, for $n \geq \sum$ and $T(1) = 1$ What is the asymptotic behaviour of $T(n)$ as a function of $n$ ?
Consider the following instance of the $0 -1$ Knapsack problem: $\max 6X_{1} + 11X_{2} + 16X_{3} + 21X_{4} + 26X_{5}$ Subject to $4X_{1} + 8X_{2} + 12X_{3} + 16X_{4} + 20 X_{5} < 32$ and $X_{i}=0$ or $1$ for $i=1,\dots,5$. ... . Number the nodes in the tree in the order in which they are expanded and for each node show the bound on the partial solutions and the decision which leads to that node.
The following program computes values of a mathematical function $f(x)$. Determine the form of $f(x)$. main () { int m, n; float x, y, t; scanf ("%f%d", &x, &n); t = 1; y = 0; m = 1; do { t *= (-x/m); y += t; } while (m++ < n); printf ("The value of y is %f", y); }