Greedy Optimized Subset-Sum Problem

Question

Given positive integers $a_1,...,a_n,b$, find $x_1,...,x_n \in \{0,1\}$ such that $a_1x_1 + ... + a_nx_n \lt b$ but is as large as possible.

How do I show that there is a greedy algorithm to this problem and how do I estimate its performance versus the optimized problem.

Any help would be appreciated, not really sure where to start with the problem.

Thanks.

Answer 1

Each variable $x_j$ is boolean in spirit: it indicates if you include $a_j$ in the sum or not. The greedy algorithm would do the following:

1. Order $a_j$ by size: $a_1\ge a_2\ge \dots$
2. Introduce $s=0$, current sum and $j=1$, current index
3. If $s+a_j<b$, include $a_j$: that is, $s=s+a_j$
4. Increment $j$
5. If $j<n$, then return to step 3, otherwise stop.

An example where the greedy algorithm performs poorly: $a_1=51$, $a_2=50$, $a_3=50$, $b=101$. The optimal solution is $a_2+a_3=100$, but the greedy algorithm chooses $a_1=51$.

You can try to prove that the greedy algorithm will always get at least the half of the maximal possible amount.