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 $)