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

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

Answer 1

[David Hill]

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]

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.

Really appriciate your help :)

Answer 2

[John D'Errico]

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]

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 :)