Намерете комбинацията от числа, която е възможно най-близка до определено число

Имам вектор 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 без повторение на елементи. B) Сумата на всеки вектор е по-малка от 400. C) Всички елементи на вектор 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