20.01.2012, 18:04
общий
это ответ
Здравствуйте, Sanek!
Вот решение первой задачи рекурсивным поиском с возвратом. Пытался как-то оптимизировать процесс -- но, кажется, здесь нет возможностей для отсечения каких-то ветвей рекурсии. Т.е. получился по сути полный перебор всех допустымых вариантов распределения средств.
Насчёт жадного алгоритма я удивлен. В данной задаче я не вижу возможности для его осмысленного применения.
[code h=200]const dohod_tabl:array[1..5,0..7] of real=
((0, 0.86, 0.95, 1.66, 2.52, 2.81, 3.45, 4.28),
(0, 0.87, 1.78, 2.22, 2.57, 3.0, 3.0, 3.77),
(0, 0.09, 0.77, 0.92, 0.97, 0.99, 1.64, 2.55),
(0, 0.43, 0.67, 1.32, 1.34, 1.48, 2.03, 2.49),
(0, 0.3, 0.64, 1.25, 2.23, 2.38, 3.09, 3.87));
var vlozh,vlozh_max:array[1..5] of integer;
dohod,dohod_max:array[1..5] of real;
i,j:integer;
procedure GetDohodMax(i:integer;sum:integer);
var n:integer;
begin
if sum>=0 then {Проверка наличия денег (по сути перестраховка
-- это обеспечивается алгоритмом)}
if (i<5) then {Терминальное условие: не дошли до последнего предприятия}
begin
for n:=sum downto 0 do {Перебираются возможные вложения в передалх оставшейся суммы}
begin
vlozh[i]:=n; {Задаётся вложение в i-е предприятие}
dohod[i]:=dohod[i-1]+dohod_tabl[i,n]; {вычисляется доходность от сделанного вложения}
GetDohodMax(i+1,sum-n); {Рекурсивный вызов для следуюущего предприятия
с оставшейся суммой}
end
end
else begin
vlozh[5]:=sum; {В последнее предприятие вкладывается вся оставшаяся сумма}
dohod[5]:=dohod[4]+dohod_tabl[5,sum];
if dohod[5]>dohod_max[5] {Сравнение максимумом из предыдущих раскладов}
then begin
dohod_max:=dohod;
vlozh_max:=vlozh;
end;
end
end;
begin
{Начальное состояние}
for i:=1 to 5 do
begin
vlozh[i]:=0;
vlozh_max[i]:=0;
dohod[i]:=0;
dohod_max[i]:=0
end;
{Решение задачи}
GetDohodMax(1,7);
{Вывод на экран}
write('Predpriyatie ');
for i:=1 to 5 do
write(i:5);
writeln;
write('Vlozhenie ');
for i:=1 to 5 do
write(vlozh_max[i]:5);
writeln;
write('Dohod (narast.itog)');
for i:=1 to 5 do
write(dohod_max[i]:5:2);
writeln;
readln;
end.[/code]