How to get the best combination of element to approach a value?
10 views (last 30 days)
Show older comments
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
Accepted Answer
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)
3 Comments
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
More Answers (1)
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,:)
3 Comments
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,:)
See Also
Categories
Find more on Calendar in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!