How to get the best combination of element to approach a value?

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

[Steven Lord]

See the Wikipedia page for the subset sum problem for some discussion of a similar problem.

Answer 1

[Bruno Luong]

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)

[Nathan Badier]

Thanks for your answer, however is there a way to allow to overshoot a little the value to get closer.

For example with the value 14080 I get the combination [68,150,270,560,1000,2200,9400] for a result of 13648. But with just 9400 and 4700 I can get 14100 wich is closer.

[Bruno Luong]

Sorry this is due to a BUG of my A matrix

a = [68,150,270,560,1000,2200,4700,9400] ;
val = 14080 

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

[Nathan Badier]

Thanks a lot, works perfectly

Answer 2

[KSSV]

Use this file exchange: https://www.mathworks.com/matlabcentral/fileexchange/11462-n_permute_k to get different permutations of selecting k out of n. You will get indices, and pick elements from a aaccordingly. Get sum and use knnsearch to get the nearest element. Or get the difference and pick minimum.

a=[68,150,270,560,1000,2200,4700,9400] ;
val = 7611 ; % value you want to check for sum 
% select values 
n = 4 ; % select n out of length(a)=8; change it accordingly  
[M,idx] = npermutek(a,4) ; % get all permutations 
thesum = sum(M,2) ; % get sum 
[val,idx] = min(abs(thesum-val)) ; % find the closest one to val 
iwant = M(idx,:)

[Nathan Badier]

Thank you,

However I don't know in advance the number of element needed for my combination, it could be the sum of all element as well as just one. Moreover I don't want repetitions. I was hoping to avoid calculating all possible combinations to have a less demanding function

[KSSV]

Put a loop for n. And fix the criteria on how close the value should be.

[KSSV]

Actually you can use nchoosek to avoid repititions.

a=[68,150,270,560,1000,2200,4700,9400] ;
val = 7611 ; 
% select values 
n = 4 ; 
M = nchoosek(a,4) ; 
thesum = sum(M,2) ; 
[val,idx] = min(abs(thesum-val)) ; 
iwant = M(idx,:)