takya.ru страница 1
скачать файл


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

Применим метод динамического программирования. Предварительно упорядочим задания по возрастанию Di. Подзадача с параметрами (i, j): пусть студент выполнил какие-то задания из заданий с 1-го по i-е и потратил на выполнение заданий j дней. Пусть c(i, j) — решение подзадачи с параметрами (i, j). Для вывода рекуррентного соотношения заметим, что студент мог либо выполнить i-е задание, либо нет. Рекуррентное соотношение:



c(i, j) = max{c(i – 1, j), c(i – 1, jLi) + Ri}.

program rating;

const

maxN = 1000;



maxD = 2000;

var


c, p: array[0..maxN, 0..maxD] of integer;

d, r, l: array[1..maxN] of integer;

num: array[1..maxN] of integer;

n: integer;

res, best: integer;

i, j: integer;


function max(a, b: integer): integer;

begin


if (a > b) then

Result := a

else

Result := b;



end;
procedure swapint(var a, b: integer);

var


tmp: integer;

begin


tmp := a;

a := b;


b := tmp;

end;
procedure rec(i, j: integer);

begin

if (p[i-1, j-l[i]] <> 0) then



rec(p[i-1, j-l[i]], j-l[i]);

writeln(num[i], ' ', j-l[i]+1);

end;
begin

assign(input, 'input.txt');

reset(input);

assign(output, 'output.txt');

rewrite(output);
read(n);

for i := 1 to n do

begin

read(l[i], d[i], r[i]);



num[i] := i;

end;
for i := 1 to n do

begin

for j := i+1 to n do



begin

if (d[i] > d[j]) then

begin

swapint(d[i], d[j]);



swapint(r[i], r[j]);

swapint(l[i], l[j]);

swapint(num[i], num[j]);

end;


end;

end;
FillChar(c, SizeOf(c), 0);

FillChar(p, SizeOf(p), 0);

for i := 1 to n do

begin

for j := 1 to maxD do



begin

c[i, j] := c[i-1, j];

p[i, j] := p[i-1, j];

if (j >= l[i]) and (j <= d[i]) then

begin

if (c[i-1, j-l[i]]+r[i] > c[i, j]) then



begin

c[i, j] := c[i-1, j-l[i]]+r[i];

p[i, j] := i;

end;


end;

end;


end;
res := 0;

best := 0;

for i := 1 to maxD do

begin


if (c[n, i] > res) then

begin


res := c[n, i];

best := i;

end;

end;
writeln(res);



if (res > 0) then

rec(p[n, best], best);


close(input);

close(output);



end.

скачать файл



Смотрите также:
Подзадача с параметрами
17.73kb.
Рабочая программа по элективному курсу «Задачи с модулями и параметрами» для 9 класса учителя первой квалификационной категории
124.37kb.
Программа элективного курса по математике «Текстовые задачи с параметрами»
265.07kb.
Алгоритмы управления с итеративным обучением системами с неопределенными параметрами и возможными нарушениями
109.34kb.
Иванов И. И., к т. н., доцент
53.66kb.
Графические системы
26.27kb.
Пояснительная записка по дисциплине ‘Электроника’ студент группы Т28-219 Горбачев Андрей г. Уфа 2003г
128.83kb.
«Задачи и уравнения с параметрами» на 2013 2014 учебный год
209.6kb.
Измерение основных параметров операционных усилителей и исследование работы инвертирующих и неинвертирующих схем их включения
155.69kb.
Факторный анализ Этапы выполнения факторного анализа 1
194.04kb.
Урока: «Решение вычислительных задач с использованием подпрограмм с параметрами»
43.4kb.
Мультивибраторы
57.78kb.