# Combination of two values in a list to get the value of an input value

2 views (last 30 days)
kalana agampodi on 8 Sep 2022
Commented: kalana agampodi on 15 Sep 2022
Hi,
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;
num2= 1850;
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;
d=50;%small difference
A=[];
for k=1:length(list)
n=nchoosek(list,k);
s=sum(n,2);
f=find((num-s)<=0&(num-s)>=-d,1);
if ~isempty(f)
A=n(f,:);
break;
end
end
A
A = 1×3
200 500 1200
kalana agampodi on 15 Sep 2022
Thanks a lot.
Can you please explain the code a bit ?
f=find((num-s)<=0&(num-s)>=-d,1);
I coudnt figure out affter this line of code.

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)
List = 1×12
3 7 13 19 29 37 43 53 61 71 79 89
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)
LP: Optimal objective value is -100.000000. Cut Generation: Applied 1 clique cut. Lower bound is -100.000000. Heuristics: Found 1 solution using total rounding. Upper bound is -96.000000. Relative gap is 4.12%. Heuristics: Found 1 solution using diving. Upper bound is -100.000000. Relative gap is 0.00%. Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).
Xsol = 12×1
0 0 0 0 1.0000 0 0 0 0 1.0000
fsol = -100
exitflag = 1
List(find(Xsol))
ans = 1×2
29 71
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.
kalana agampodi on 15 Sep 2022
Thanks, No it is not homework or school related. I have a LTC 6993-4 pulse width (PW) generator. PW is proportional to the Resistors I use. I am trying to figure out combinations of two resistors that gives me the PW that I require to drive my motor.
Thanks for the help :)