# Minimal set with subsets that sum to given values

I'm sure this is a solved problem but I don't know what to search for:

I have a set of positive numbers (256 at the moment but it could get bigger) and I need to find another set of positive numbers such that for each number in the original set, there is a sub set of the new set that sums to within some error bound of the number:

• Give $S\subset\mathbb{R}^+$
• Find a small set $P\subset\mathbb{R}^+$
• Sutch that $\forall i\in S, (\exists P_i\subset P,|i-\sum P_i|\le\epsilon)$

The best solution I have found so far is itterative:

• find $M = max(S_n)$.
• find $m = min(x | x \in S_n \wedge x > M/2)$
• $P_{n+1} = P_n \cup m$
• $S_{n+1} = (x | x \in S_n \wedge x < m) \cup (x - m | x \in S_n \wedge x \ge m)$
• Stop when the approximation is good enough (i.e. $\forall x\in P_n,x\le\epsilon$)
-
By $\sum P_i = i \pm \epsilon$, you mean $\left|i - \sum P_i\right| \le \epsilon$, yes? – Rahul Sep 20 '10 at 5:30
By "a small set $P$ contained in the positive reals" do you mean contained in $S$ or in $\mathbb{R}^+$? Also this is very much not set theory. Maybe combinatorics, I don't know. – Asaf Karagila Sep 20 '10 at 7:46
@Rahul: yes, that is correct. You can edit that in if you want. – BCS Sep 20 '10 at 14:50
@Asaf: $\mathbb{R}^+$ – BCS Sep 20 '10 at 14:53

And a counter example: [1, 2, 3, 5, 8], $3+5=8$: remove 8, $2+3=5$: remove 5, $1+2=3$: remove 3. 5 and 8 can't be formed. – BCS Sep 20 '10 at 14:59