CODEWITHSUNDEEP
algorithmmatlabcombinatoricsheuristics
ayca altay
ayca altay

Reputation: 51

Find the combination of numbers that is a close as can be to a specific number

I have a vector A, that is 

A = [300; 165; 150; 150; 400; 300; 80; 250; 165; 80; 200]

I am trying to find a set of vectors that are composed of the elements of this vector A so that their elements sum up to a value as close as possible to 400 and so that all elements of vector A are included in the disjoint set of vectors.

For example, 400 is already 400, so this is first set of vectors without a slack.

Another set would be the vector of [250 150], their sum is 400.

Another two can be two sets of the vector [300 80], their sum is 380, so a slack of 20 is compromised.

Another would be [165 165], they sum up to 330, with a slack of 70. The last one would be 200 and 150, with a slack of 50. The total slack is 20+20+70+50=160.

I'm trying to find a heuristic or an algorithm (not a programming model) that would minimize the slack. I'm coding in Matlab.

Upvotes: 0

Views: 142

Answers (2)

aarbelle
aarbelle

Reputation: 1033

You could try something like this:

v = [300; 165; 150; 150; 400; 300; 80; 250; 165; 80; 200];
binarystr = dec2bin(1:(2^(length(v))-1));
bincell = mat2cell(binarystr,ones(size(binarystr ,1),1),ones(size(binarystr ,2),1));
bin = cellfun(@(x) str2double(x),bincell);

Now you can multiply to find all the combinations:

comb = b*v;

Find the minimum

target = 400;
[val,index] = min(abs(comb-target));

if you want to know what the combination was the you can look for the indexes:

idxs = find(bin(index,:));

and the values are:

disp(idxs)
disp(v(idxs))

Hope this helps.

Upvotes: 1

GameOfThrows
GameOfThrows

Reputation: 4510

So I thought this was a very interesting problem and started it at work (I hope my boss won't find out), but I am missing a part. The code is pretty much horrible, but I wanted to show the concept I guess. 

A = [300; 165; 150; 150; 400; 300; 80; 250; 165; 80; 200] ;



P = (1 - (sum(A) /400 - floor(sum(A)/400))) * 400; %//minimum slack to be achieved



%//Round 1
G1 = zeros(floor(sum(A)/400)+1,3)
for t = 1:floor(sum(A)/400)+1
 if size(A,1) > 1
%//single combination
[F indF] = min(abs(A-400));
%//double combination
if size(A >1)
D = combntns(A,2);
sumD = sum(D,2);
[F2 indF2] = min(abs(sumD-400));
end
%//triple combination
if size(A >2)
T = combntns(A,3);
sumT = sum(T,2);
[F3 indF3] = min(abs(sumT-400));
end
%remove 1
[R removeInd] = min([F,F2,F3]);
if removeInd == 1
    G1(t,1) = A(indF);
    A(indF) =[];
else if removeInd ==2
     G1(t,1:2) = D(indF2,:)   ;
     [tmp,tmp2] = intersect(A,G1(t,:));
     A(tmp2) = [];
    else removeInd == 3
        G1(t,:) = T(indF3,:)   ;
        [tmp,tmp2] = intersect(A,G1(t,:));
        A(tmp2) = []      ;
    end
end     



else if size(A,1) == 1
         G1(t,1) = A;
     end
 end



end



    </pre></code>




the results:



>>400   0   0
  150   250 0
  165   150 80
  300   80  0
  165   200 0
  300   0   0




The reason the results were wrong is because I searched for subsets with length of 1,2 and 3. 4 is not possible, since it produce huge results (but you can include it anyways). If I switch to subsets with length of 1 and 2 I get the right answer. So I think the step I am missing is how long my subsets can be. 



results when max length of subset is set to 2:


>>400   0   0
  150   250 0
  300   80  0
  300   80  0
  165   200 0
  165   150 0

All you have to do is % out the triple combination, and change this line : [R removeInd] = min([F,F2]); without F3

Upvotes: 0

Related Questions