Найдите комбинацию чисел, максимально близкую к определенному числу

У меня есть вектор A, то есть

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

Я пытаюсь найти набор векторов, составленных из элементов этого вектора A так, чтобы их элементы суммировались со значением, максимально близким к 400, и чтобы все элементы вектора A включались в непересекающийся набор векторов .

Например, 400 — это уже 400, так что это первый набор векторов без резерва.

Другой набор будет вектором [250 150], их сумма равна 400.

Еще два могут быть двумя наборами вектора [300 80], их сумма равна 380, поэтому резерв 20 скомпрометирован.

Другой будет [165 165], они в сумме дают 330 с резервом 70. Последний будет 200 и 150 с резервом 50. Общий резерв 20+20+70+50=160.

Я пытаюсь найти эвристику или алгоритм (не модель программирования), который минимизировал бы слабину. Я кодирую в Matlab.


matlab algorithm combinatorics heuristics
person ayca altay    schedule 15.10.2015    source источник
comment
Вам придется быть немного более конкретным. Вы пытаетесь разбить свой набор на непересекающиеся наборы, чтобы их объединение содержало все элементы вашего исходного набора?   -  person BillBokeey    schedule 15.10.2015
comment
Точно. Я пытаюсь разделить их на непересекающиеся множества, и их объединение должно содержать все элементы исходного множества. Я решил проблему, используя смешанное целочисленное программирование, но мне нужен другой способ.   -  person ayca altay    schedule 15.10.2015
comment
Уточните, пожалуйста, употребление слова «множество». Я думаю, вы хотите сказать, что набор — это комбинация векторов, которые удовлетворяют вашим ограничениям.   -  person JaBe    schedule 15.10.2015
comment
Спасибо, немного отредактировал. Надеюсь, теперь стало понятнее.   -  person ayca altay    schedule 15.10.2015
comment
@aycaaltay Я бы все же понял, что набор - это набор векторов, который удовлетворяет ограничениям: A) Векторы состоят из элементов A без повторения элементов. Б) Сумма всех векторов меньше, равная 400. В) Все элементы вектора A принадлежат одному из векторов.   -  person JaBe    schedule 15.10.2015
comment
Является ли резерв направленным, т. е. если сумма равна 420, резерв будет равен -20, а общий резерв будет рассчитываться с помощью -20?   -  person Divakar    schedule 15.10.2015
comment
Это NP-сложно из-за сокращения проблемы раздела. Однако вы можете использовать динамическое программирование, чтобы решить его за O (w * n), где w — максимальное значение, а n — количество элементов массива.   -  person Niklas B.    schedule 15.10.2015

Ответы (2)


arrow_upward
1
arrow_downward

Вы можете попробовать что-то вроде этого:

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

Теперь вы можете умножить, чтобы найти все комбинации:

comb = b*v;

Найдите минимум

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

если вы хотите узнать, какая комбинация была, вы можете поискать индексы:

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

и значения:

disp(idxs)
disp(v(idxs))

Надеюсь это поможет.

person aarbelle    schedule 15.10.2015

arrow_upward
0
arrow_downward

Итак, я подумал, что это очень интересная проблема, и начал ее на работе (надеюсь, мой босс не узнает), но я упускаю часть. Код в значительной степени ужасен, но я хотел показать концепцию, я думаю.

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




Причина, по которой результаты были неправильными, заключается в том, что я искал подмножества длиной 1,2 и 3,4, что невозможно, так как это дает огромные результаты (но вы все равно можете включить его).  Если я переключаюсь на подмножества длиной 1 и 2, я получаю правильный ответ.  Поэтому я думаю, что шаг, который мне не хватает, - это то, насколько длинными могут быть мои подмножества.



результаты, когда максимальная длина подмножества установлена ​​​​на 2:


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

Все, что вам нужно сделать, это % из тройной комбинации и изменить эту строку: [R removeInd] = min([F,F2]); без F3

person GameOfThrows    schedule 15.10.2015
comment
для подмножеств максимальной длины 4 и т. д. вы можете либо написать еще один цикл (который будет вложенным циклом), либо вы можете написать его, как я, но я думаю, что это решение. - person GameOfThrows; 15.10.2015