program selection iinput,outputy,

[поиск оптимальной выборки объектов при ограничениях^] const п - 10; type index = 1.. ;

object ~ record v,wi integer evA; var /: index ,

a: ansy[index]otohJecti

limw, totv, maxv: integer;

H-1, w2, wi: integer;

s, opts: set of index;

z: array [boolean] of char;

procedure try(i: index; tw,avi integer); var avi: integer;

Jbegln [попытка включения объекта i]-

if tw + a[i] .w limw then begin s := s + [i];

if i < n then try(i+l, tw-}-a[i].w, av) else it av > maxv then begin maxv := av; opts i~ s end ; s:s- И end ;

[попытка исключения объешпа i] avl :== av - a[i] Vl if avl > maxv then

begin if i < n then try(}-\-l, tw, avl) else begin 7 tfw \= аю1; opts :== s end

end [try];

begin foy :== 0; for г := 1 fo и do with a[i] do

begin!=з toiv -f i; end;

read(whw2,w2);

z[true] := *; г|/й&е]

writed WEIGHT 0;

for г 1 to n do write (op] .w: 4);

smVe/я; tmVe С VALUE

for г := 1 to л do write (a[i] .v; A);

writeln;

repeat limw :~ wl; maxv := 0; j := [ ]; opts :~ [ ];

try(\,0,totvy, write{limw);

for I := 1 to n do writeC Jn o/jf]);

writeln; wl wl + w2 until wl > w2

Программа 3.7. Оптимальная выборка.

выборки, будет возможность получить без этого объекта такую д^щую ценность выборки, которая была бы не меньше полуденного до сих пор оптимума. Ведь иначе продолжение поиска, хотя и будет давать какие-то решения, никогда не приведет к оптимальному, следовательно, на этом пути бесполезен какой-либо дальнейший поиск. С учетом этих двух условий мы определяем, какие существенные величины нужно вычислять для каждого шага в процессе отбора:

1. Общий вес tw выборки s, полученной до сих пор.

2. Общую ценность av текущей выборки s, которой еще можно достичь.

9ти два значения удобно представить в виде параметров Лроцедуры try.

Условие включение приемлемо в (3.48) теперь можно сформулировать как

tw + a[i\.wlimw (3.50)

а последующую проверку оптимальности - как

§Н av> maxv then begin {запись нового оптимума} /q кп

opts:=s; maxv :-av Ко.Ы)

Последнее присваивание связано с тем соображением, что достижимое значение будет получено после просмотра всех п объектов.

Условие невключение приемлемо в (3.48) выражается как

av - a [i].v > maxv (3.52)

зк как позднее оно снова используется, значение av - присваивается переменной avl, чтобы избежать повторного вычисления.

Всю программу полностью теперь можно получить из с помощью (3.52), добавив соответствующие операторы Инициации глобальных переменных. Следует отметить, что ®Десь удобно используются операции над множествами.

Результат выполнения программы 3 7с заданными npeflejj, ными весами от 10 до 120 показан в табл. 3.5.

Таблица 3.5. Пример результата работы программы оптимальной

выборки

Вес 10 Значение 18

11 20

12 17

13 19

14 25

15 21

16 27

16 25

19 24

10 20 30 40 50 60 70 80 90 100 110 120

УПРАЖНЕНИЯ

3.1. (Ханойские башни.) Даны три стержня и п дисков разного размера, Диски можно надевать на стержни, строя таким образом башни : Пусть вначале диски находятся иа стержне А в порядке убывающего размера, как показано иа рис. 3.10 для п = 3. Нужно переместить п

в

Рис 3.10. Ханойские башни.

дисков на стержень С так, чтобы оии остались в том же порядке. Этого нужно добиться, соблюдая следующие правила:

1. На каждом шаге ровно один диск перемещается с одного стержня на другой.

2. Диск большего размера нельзя помещать на меньший.

3. Стержень В можно использовать в качестве промежуточного. Постройте алгоритм, который выполняет эту задачу. Заметим, ч^О башию удобно рассматривать как состоящую из одного диска на са мом верху и из башни, состоящей из остальных дисков. Опишите этот

алгоритм в Виде рекурсивной программы.