Combination of two values in a list to get the value of an input value
1 Ansicht (letzte 30 Tage)
Ältere Kommentare anzeigen
kalana agampodi
am 8 Sep. 2022
Kommentiert: kalana agampodi
am 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
0 Kommentare
Akzeptierte Antwort
David Hill
am 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
Weitere Antworten (1)
John D'Errico
am 8 Sep. 2022
Bearbeitet: John D'Errico
am 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)
List(find(Xsol))
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.
Siehe auch
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!