Процедура полного перебора

← →
inos (2007-04-22 15:32) [0]

Доброго времени суток!!! Уважаемые мастера, помогите разобраться с процедурой полного перебора. Имеется набор из n элементов a1...an. Каждый элемент ai характеризуется определенными свойствами - вес wi и цена ci. Требуется найти оптимальную выборку ai...aik из этого набора, т.е. такую, для которой при заданном ограничении на суммарный вес Wmax достигается максимальная стоимость.

type index=1..10; var s: Set of index; Procedure Vbr(i:Index); begin < включение i-го элемента в выборку Include (s,i) >; if i<n then Vbr(i+1) else < проверка приемлемости и оптимальности >; < исключение i-го элемента из выборки Exclude (s,i) >; if i<n then Vbr(i+1) else < проверка приемлемости и оптимальности >; end; // Vbr

пишу

Procedure FullPerebor(i:byte;tw,ac:cardinal); //метод полного перебора Var ac1:cardinal; begin include(S,i); if i<n then begin FullPerebor(i+1, tw+a[i].w,ac); end else begin if tw+a[i].w<=Wmax then begin if ac>maxC then begin maxC:=ac; optS:=S; end; end; Exclude(S,i); end; if i<n then begin FullPerebor(i+1,tw+a[i].w,ac); //продвижение вправо end else if tw<=Wmax then begin if ac>maxC then begin maxC:=ac; optS:=S; end; end; end; // FullPerebor

не работает

← →
default © (2007-04-22 15:47) [1]

http://algolist.manual.ru/maths/combinat/subentities.php

← →
inos (2007-04-23 00:35) [2]

> http://algolist.manual.ru/maths/combinat/subentities.php

посмотрел - мысль интересная. А с рекурсией? :(

← →
Германн © (2007-04-23 00:56) [3]

> Требуется найти оптимальную выборку ai...aik из этого набора,
> т.е. такую, для которой при заданном ограничении на суммарный
> вес Wmax достигается максимальная стоимость.

Чёртовы буржуи! Всё бы им "содрать" побольше! :-)

← →
default © (2007-04-23 01:01) [4]

inos (23.04.07 00:35) [2]

procedure Comb(var arr: Array Of Boolean; k: LongInt);
var
i: LongInt;
begin
for i := k to High(arr) do begin
arr[i] := True;
// щас arr тут представляет очередное двоичное число
// выполняем тут расчёты со стоимостью и весом
if i+1 = Length(arr) then Exit;
Comb(arr, i+1);
arr[i] := False; // откат комбинации
end;
end;

arr должен быть весь в False и иметь длину N
и делаем вызов Comb(arr, 0)

если не ошибся, то так

← →
default © (2007-04-23 01:21) [5]

procedure Comb(var arr: Array Of Boolean; k: LongInt);
var
i: LongInt;
begin
if k = Length(arr) then Exit;
for i := k to High(arr) do begin
arr[i] := True;
// щас arr тут представляет очередное двоичное число
// выполняем тут расчёты со стоимостью и весом
Comb(arr, i+1);
arr[i] := False; // откат комбинации
end;
end;

вот тяка будет пахать

рекурсию используют обычно там где она даёт короткие и понятные решения
в остальных ищи счастье в итеративном подходе
в данном случае смотри по размеру своего N
если небольшое оно может быть тогда можно и рекурсивно перебирать
но мне кажется и тебе и читающим твой код будет более понятен итеративный варианта
и помни принцип
keep it simple, stupid что в переводе
"держи это простым, тупица"

решил вот так:
Procedure FullPerebor(i:byte;tw,ac:cardinal); //метод полного перебора Var ac1:cardinal; begin include(S,i); if i<n then begin FullPerebor(i+1, tw+a[i].w,ac); end else if tw+a[i].w<=Wmax then begin if ac>maxC then begin maxC:=ac; optS:=S; end; end; Exclude(S,i); ac1:=ac-a[i].c; if ac1>maxC then if i<n then begin FullPerebor(i+1,tw,ac1); end else if tw<=Wmax then begin maxC:=ac1; optS:=S end; end; // FullPerebor

Всем спасибо!!

Процедура полного перебора Найти похожие ветки