MATLAB: How to get the best combination of element to approach a value

approximation

I have a vector a=[68,150,270,560,1000,2200,4700,9400] and i would like a function to find a combination to get the closest possible to a given value.
For example if I give the value 7611, I want to have in return the elements 4700 2200 560 160, since 4700+220+560+160=7620 is the closest to my value.
Thanks

Best Answer

EDIT CODE
If you have optimization toolbox
a = [68,150,270,560,1000,2200,4700,9400] ;
val = 7611
A = [ a, -1;
     -a, -1];
b = [val; -val];
n = length(a);
f = [zeros(n,1); 1];
lo = [zeros(n,1); 0];
hi = [ones(n,1); Inf];
x = intlinprog(f, 1:n, A, b, [], [], lo, hi);
keep = round(x(1:n))==1;
suba = a(keep)
sumsuba = sum(suba)
val
Result (yes there is a better solution than yours):
suba =
         150         560        2200        4700
sumsuba =
        7610
val =
        7611
You can test with larger array of 100 elements such as where some of the brute force method would fail miserably
a = randi(100,1,100)
val = randi(1000,1,1)
Related Question