Combination of two values in a list to get the value of an input value
2 views (last 30 days)
I have a list of number and I want to find the combination of two numbers equal to or slightly less than a value.
(This has to be a combination of two numbers from the list). An example is given below.
num1 = 700;
list = [ 200 300 500 800 1200]
ans_a = 200 & 500
ans_b = 500 & 500 & 800
David Hill on 8 Sep 2022
list = [ 200 300 500 800 1200];
num = 1850;
More Answers (1)
John D'Errico on 8 Sep 2022
Edited: John D'Errico on 8 Sep 2022
Easy, peasy. Yet, this is very possibly homework. Yet, you have already gotten an answer, that is pure brute force, when a far better answer exists. Hey, the good news is, if you turn in my answer, your teacher will absolutely KNOW you cheated, IF this was a homework assignment. Such is life.
You want to find the sum of K (I'll be general, K would be 2 in your case) numbers from a list. The sum cannot exceed a target sum, yet is as close as possible.
Is there a direct way to solve this problem in a general case? Of course. Use binary integer programming, thus intlinprog. For example...
List = primes(100); List = List(2:2:end)
So in my case, List contains every other prime number, not exceeding 100.
Now, find a sum of two elements from that list, that is as close to some target value. (If you want to think of this as a variation of Goldbach's conjecture, feel free. I've gotten creative, and chosen to use only every other prime.)
Target = 100;
K = 2;
NList = numel(List);
There are 12 elements in the list, so there are 12 unknowns. The unknowns will be all 0 or 1, but we want sum(X) to be K (here, 2.)
intcon = 1:NList;
LB = zeros(1,NList);
UB = ones(1,NList);
Do you see this makes it into a binary integer programming problem?
Aeq = ones(1,NList); beq = K; % force there to be EXACTLY 2 elements which are 1.
Aineq = List(:)'; bineq = Target; % inequality constraint to force the sum to not exceed Target
f = -List(:); % MAXIMIZE the sum
[Xsol,fsol,exitflag] = intlinprog(f,intcon,Aineq,bineq,Aeq,beq,LB,UB)
So Target was hit exactly, as 100 = 29 + 71. There may be other possible solutions of course, but this is the one found by intlinprog. Finding all possible solutions, were that your goal, would be a far more intensive problem if K were larger than 2, and probably reduce to brute force.
See that had I changed K, we could have solved the problem with more than only 2 elements in the sum.
It would be easy enough to write this as a function, that would take the list of numbers, the Target, and the number K, then returning a solution. I hope this is not your homework assignment, but I am so often disappointed on Answers.