Algorithm to take the best set of numbers to sum -

i trying find algorithm sum small amounts of money table/list equal or possibly closest(but not larger) ceratin number.

let me explain example. i've got list numbers :
{ 1.23 ; 3.45 ; 20.11 ; 100.13 ; 200.08 }

and number trying 123.69

so should take { 3.45 ; 20.11 ; 100.13 } = 123.69

if number 122 should not take same, { 20.11 ; 100.13 ; 1.23 } = 121.47

is there idea how write that?

this variation of subset-sum problem, answer classic problem involving integers pretty easy using dp, , can found in many threads around stackoverflow, this one.

however, there small tweak in problem makes different classic integer subset-sum problem - dealing values don't have integers, have decimal value.

it seems in case, decimal value 2 digits "after dot". means, can transform problem classic integers subset-sum problem multiplying values in array 100, , search 100*x instead of x.
in example - need 12,369 in array of integer values {123, 345, 2011, 10013, 20008}.

---

attachment 1: solving subsetsum problem integers:
this done using dynamic programming, recursive formulas dp is:

f(x,0) = false if x<0 f(0,0) = true f(x,i) = f(x,i-1) or f(x-arr[i], i-1) 

by calculating above bottom-up, matrix of size (w*100+1) x (n+1) (where w requested sum , n number of elements in array).

by searching column in last row holds value true when done - found "best" possible sum number.

---

attachment 2: finding actual subset of numbers.
by now, have found best sum can get, not best numbers yet. in order so, need use matrix (which calculated previously), , replay steps did in order generate sum. explained similar problem in this thread, , in nutshell done by:

line <- best //best solution found <- n while (i> 0):   if table[line-array[i]][i-1] == true:       element 'i' in set       <- i-1       line <- line-array[i]   else:       <- i-1  

---

note: if complex, , size of arrays small, or alternatively "2 decimals after dot" restriction not true - pretty have use exponential solution - brute force, creates possible subsets, , chooses best out of them. there no (known) efficient solution in case because problem known np-hard

---

tl;dr: multiply values 100, , use existing integers subset-sum problem algorithm find best fit.