3 views (last 30 days)
Nathan Badier on 8 Sep 2020
Edited: Bruno Luong on 10 Sep 2020
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

#### 1 Comment

Steven Lord on 8 Sep 2020
See the Wikipedia page for the subset sum problem for some discussion of a similar problem.

Bruno Luong on 9 Sep 2020
Edited: Bruno Luong on 10 Sep 2020
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 on 9 Sep 2020
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 on 9 Sep 2020
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 on 10 Sep 2020
Thanks a lot, works perfectly

KSSV on 8 Sep 2020
Edited: KSSV on 8 Sep 2020
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 on 8 Sep 2020
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 on 8 Sep 2020
Put a loop for n. And fix the criteria on how close the value should be.
KSSV on 9 Sep 2020
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,:)