Задача 13 Лесенки Лесенкой называется набор кубиков, в котором каждый более верхний слой содержит кубиков меньше, чем предыдущий.

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

Входные данные

Во входном файле записано число N (1N100).

Выходные данные

В выходной файл вывести искомое число лесенок.

Пример

Input.txt	Output.txt
3	2

Переформулируем нашу задачу на язык математики. В каждом следующем слое (считая сверху вниз) кубиков больше, чем в предыдущем, а в сумме их n. Значит, нам требуется представить n в виде суммы возрастающих натуральных слагаемых.

---

1 | |

---------

4 | | | | |

-----------

5 | | | | | |

-----------------

8 | | | | | | | | |

-----------------

n=1+4+5+8

Пусть в качестве первого слагаемого мы взяли L, тогда нам требуется n-L разбить на слагаемые. Но теперь добавляется дополнительное условие - слагаемые должны быть больше либо равны L+1. Значит, нам достаточно научиться считать число разбиений числа n на слагаемые не меньшие k (обозначим a_n,k). Есть два случая: слагаемое k либо входит в разбиение (таких способов a_n-k,k+1), либо нет (таких способов a_n,k+1). Так как никакое разбиение не подходит одновременно под оба эти случая, то a_n,k=a_n-k,k+1+a_n,k+1 Заметим, что для единицы существует единственное разбиение: 1 = 1. Значит a_1,0 = a_1,1 = 1, a_1,f = 0, где f >= 2. a_n,k удобно вычислять в порядке невозрастания k. При равных k - в произвольном порядке. Данный алгоритм выполняет порядка N² действий.

program lesenki;

const nmax=100;mmax=100;

Var

a:array[0..nmax,0..mmax] of integer;

i,j,n,t,k:integer;

Begin

assign(input,'input.txt');

reset(input);

assign(output,'output.txt');

rewrite(output);

read(n);

for j:=1 to n do заполняем первую строку нулями

a[1,j]:=0; первые два элемента 1

a[1,0]:=1;

a[1,1]:=1;

for j:=1 to n do один способ представить число j

слагаемыми

a[j,j]:=1; не меньшими j

a[2,1]:=1;a[2,2]:=1;a[2,0]:=1; заполняем вторую строчку для числа 2

for i:=3 to n do перебираем строки, начиная с третьей

begin

k:=i-1; начиная с этого столбца

while k>0 do двигаемся к первому

begin

a[i,k]:=a[i-k,k+1]+a[i,k+1]; и вычисляем элементы матрицы

dec(k);

end;

end;

write(a[n,1]); выводим результат

End.

динампрогрзадачи

Задача 14 Шаблон и слово

Будем рассматривать слова из больших латинских букв и шаблоны, состоящие из больших латинских букв и символов "?" и "*". Говорят, что слово подходит под шаблон, если в шаблоне можно заменить каждый символ "?" на большую латинскую букву, а каждый символ "*" - на

последовательность (возможно, пустую) больших латинских букв, так, чтобы получилось требуемое слово. Напишите программу, которая определит, подходит ли слово под шаблон.

Входные данные:

в первых двух строках записаны шаблон и слово:

в одной строки записан шаблон - последовательность больших латинских букв, "?" и "*", в другой - слово, состоящее только из больших латинских букв (строки короче 256 символов).

Выходные данные: вывести YES, если слово подходит или NO, если нет.

Пример:

Input.txt	Output.txt
ABBCDA A*CDA	YES
AADAAVA A*DA*AA*	NO

Для начала определим, какая из введенных строк является словом, а какая - шаблоном. Та строка, в которой есть символы '?' или '*' - шаблон. Если ни в одной из строк их нет, то в качестве шаблона возьмем произвольную. Будем определять, может ли часть слова (обозначим s1)с 1-го по k-й символ соответствовать части шаблона (обозначим s2)с 1-го по m-й символ (обозначим a_k,m). Теперь есть 3 варианта:

• В шаблоне на m-м месте стоит буква. Тогда она соответствует последней букве слова и a_k,m=(s1[k]=s2[m]) and a_k-1,m-1

• В шаблоне на последнем месте стоит '?'. Тогда он соответствует последней букве слова и a_k,m=a_k-1,m-1

• В шаблоне на последнем месте стоит '*'. Тогда возможны два варианта: либо этой звездочке соответсвует пустая последовательность букв слова, либо непустая. Во втором случае в части слова с 1-го по k-1-й символ этой звездочке тоже соответствует некоторая последовательность букв (возможно пустая). Таким образом a_k,m=a_k-1,m or a_k,m-1.

Осталось рассмотреть несколько моментов. Так как '*' может соответствовать пустая последовательность букв, то непустому шаблону вполне может соответствовать пустое слово, значит матрица a должна индексироваться не от 1, а от 0. Если же один из индексов отрицательный - то это всегда FALSE. Заметим, что абсолютно аналогично можно решать задачу про соответсвие двух шаблонов. Просто добавятся еще несколько случаев.

program shablon_slovo;

const nmax=100;

var a:array[0..nmax,0..nmax] of boolean;

tmp,s1,s2:string;

i,j,k,m:integer;

begin

assign(input,'input.txt');

reset(input);

assign(output,'output.txt');

rewrite(output);

readln(s1);

readln(s2);

for i:=1 to length(s2) do выбираем строку, которая

будет шаблоном

if (s2[i]='*') or (s2[i]='?')

then

begin tmp:=s1; s1:=s2; s2:=tmp; break; end; меняем строки местами

k:=length(s1);

m:=length(s2);

a[0,0]:=true;

for i:=1 to k do заполняем матрицу

for j:=1 to m do

begin

if s1[i] in ['A'..'Z'] если символ буква

then a[i,j]:=(s1[i]=s2[j]) and a[i-1,j-1];

if s1[i]='?' then a[i,j]:=a[i-1,j-1]; если символ знак вопроса

if s1[i]='*' then a[i,j]:=a[i-1,j] or a[i,j-1]; если символ звездочка

end;

if a[k,m] then write('YES') else write('NO'); выводим результат

close(input); close(output);

end.

динампрогрзадачи

Задача 15 Рюкзак 1_1

Найдите максимальный вес золота, который можно унести с рюкзаком вместительностью W килограмм, если есть N слитков массой a₁,a₂, … a_n килограмм. Все веса — натуральные числа, не превосходящие 100000.

Входные данные:

В первой строке входного файла записаны два числа —N и W (1  N  300,1  W  10000). Далее следует N чисел — веса слитков.

Выходные данные:

Выведите искомый максимальный вес.

Пример:

Input.txt	Output.txt
2 10 5 6	6

В этой задаче можно считать, что все слитки в одном экземпляре и в решении можно обойтись одномерным массивом.

Program rjkzak;

const nmax = 10000;

var i,j,w,n, k, s,ans : longint;

b : array [0..nmax] of boolean;

begin

assign(input,’input.txt’);

reset(input);

assign(output,’output.txt’);

rewrite(output);

read(n,w);

fillchar(b,sizeof(b),false);

b[0]:= true;

for i:= 1 to n do перебираем слитки

begin

read(x); считываем вес очередного слитка

for j:= w-x downto 0 do выясняем можно ли взять этот слиток, перебирая

все веса от s-x до 0

if b[j] если к набранному весу j можно добавить

then b[j+x]:= true; последний слиток, то берем его

end;

for i:= w downto 0 do выводим максимальный вес взятых слитков

if b[i] then

begin

ans:= i;

break;

end;

write(ans);

close(input); close(output);

end.

динампрогрзадачи

Задача 16 Рюкзак 1_2

Имеется набор N предметов различного веса и разной стоимости. Максимальный вес рюкзака W. Набрать в рюкзак предметы максимальной стоимости, совокупный вес которых не превышает вес рюкзака. Все предметы в одном экземпляре.

Входные данные:

В первой строке входного файла записаны два числа — N и W (1  N  300;1  W  10000). Во второй строке N чисел — веса предметов и в третьей строке N чисел – стоимости предметов. Все числа не превышают 30000.

Выходные данные:

Выведите в первой строке искомую максимальную стоимость, а во второй номера взятых предметов.

Пример:

Input.txt	Output.txt
4 6 2 3 1 4 50 90 30 140	190 1 4

Пусть элемент Ci массива C соответствует стоимости i-го предмета, а элемент Vi массива V - весу i-го предмета. Будем считать, что предметы пронумерованы в порядке их следования в таблицах. Пусть A обозначает функцию, значение которой соответствует решению нашей задачи. Аргументами функции является количество предметов (по этому аргументу можно определить их стоимости и веса соответствующих предметов), а также максимальный суммарный вес, который можно взять. Определим подзадачи A(i, j), где i обозначает количество начальных предметов, из которых можно осуществлять выбор, а j определяет максимально возможный суммарный вес взятых предметов. Отметим, что определенный таким образом первый параметр i определяет как количество предметов для подзадачи,

так и значения их стоимостей и весов, определяемых из массивов C и V. Определим сначала начальные значения функции А. При нулевых значениях одного из аргументов значение функции равно нулю:

A(0,0)=0

A(0,j)=0 при j>=1,

A(i,0)=0 при i>=1.

Определим возможные значения функции A(i, j) при ненулевых значениях аргументов.

Решение подзадачи, соответствующей функции A(i, j) может быть сведено к двум возможностям: уносится ли при наилучшем решении предмет с номером i или нет.

Если предмет не берется, то решение задачи с i предметами сводится к решению подзадачи с i-1 предметами, т. е. A(i,j)=A(i-1,j).

Если предмет c номером i берется, то это уменьшает максимально возможную суммарную массу для i-1 первых предметов на величину V[i], одновременно при этом увеличивая значение решения для оставшихся предметов A(i-1,j-v[i]) на величину C[i], т. е. A(i,j)=A(i-1,j-v[i])+C[i].

При этом необходимо учитывать, что вторая ситуация возможна только тогда, когда вес i-го предмета не больше значения j. Для получения наилучшего решения необходимо выбрать лучшую из этих двух возможностей. Поэтому рекуррентное соотношение при i>=1 и j>=1 имеет вид

A(i,j)=A(i-1,j) при j<v[i] и

A(i,j)=max(A(i-1,j),A(i-1,j-v[i]) + C[i]) при j>=v[i].

Пусть заданы следующие значения стоимости и весов для 5 предметов:

C[1] = 5 V[1] = 4

C[2] = 7 V[2] = 5

C[3] = 4 V[3] = 3

C[4] = 9 V[4] = 7

C[5] = 8 V[5] = 6

W=16

Таблица значений функции T, которую мы также назовем T, выглядит следующим образом:

i\j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 5 5 5 5 5 5 5 5 5 5 5 5 5

2 0 0 0 0 5 7 7 7 7 12 12 12 12 12 12 12 12

3 0 0 0 4 5 7 7 9 11 12 12 12 16 16 16 16 16

4 0 0 0 4 5 7 7 9 11 12 13 14 16 16 18 20 21

5 0 0 0 4 5 7 8 9 11 12 13 15 16 17 19 20 21

Следовательно, решение задачи A(5,16)=21. Однако это не значит автоматически, что суммарный вес взятых предметов равен 16,он может быть и меньше. Действительно, A(1,16)=5, а соответствующая этой подзадаче суммарный вес предметов равен 4.

Для выяснения номеров элементов, вошедших в множество взятых предметов, достаточно, начав с элемента с индексами [i,j] (которые вначале равны N и W соответственно),сравнить его со значением a[i-1,j]. Если значения равны, то i элемент не входит в множество, а процесс повторяется для элемента с индексами [i-1,j]. В случае неравенства элементов элемент i входит в множество, а процесс повторяется для элемента с индексами [i-1,j-V[i]]. Процесс выполняется для всех i от N до 1.

Const MaxN=50;

MaxW=600;

Var a:Array [0..MaxN,0..MaxW] Of Word;

v,c:Array [1..Maxn] of integer;

i,j,N,W:Integer;

function max(x,y:integer):integer;

begin

if x>y then max:=x

else max:=y;

end;

Procedure Init;

Begin

Assign(input,'input.txt');

Reset(input);

Assign(output,'output.txt');

Rewrite(output);

read(n);read(w);

for i:=1 to n do

read(v[i]);

for i:=1 to n do

read(c[i]);

End;

Procedure Solve;

Var t:Integer;

Begin

FillChar(a,SizeOf(a),0);

For i:=1 to n do цикл по видам предметов

for j:=1 to w do цикл по набранному весу

if j >= v[i] если набираемый вес j больше веса i-го

предмета, т.е.

then предмет можно взять

a[i, j]:= max(a[i-1,j],a[i-1,j-v[i]]+C[i]) выбираем лучший результат

else

a[i, j]:=a[i-1,j] предмет i не берем

End;

Procedure OutWay(i,j:integer);

Begin

If i=0 если предметы кончились,то

Then Exit выходим

Else Begin иначе

if a[i,j]=a[i-1,j] если i-ый предмет не взяли

then outway(i-1,j) переходим на строку выше и вызываем

outway

else

begin

outway(i-1,j-v[i]); если взяли, то переходим на строку

выше в клетку с весом j-v[i]

write(i,' '); выводим i

end;

End;

End;

Begin

Init;

Solve;

Writeln(a[n,w]); выводим максимальную стоимость взятых

предметов

OutWay(n,w); выводим номера взятых предметов

End.

динампрогрзадачи

Задача 17 Рюкзак 2

Имеется набор N предметов различного веса и разной стоимости. Максимальный вес рюкзака W. Набрать в рюкзак предметы максимальной стоимости, совокупный вес которых не превышает вес рюкзака. Предметов каждого типа бесконечно много.

Входные данные:

В первой строке входного файла записаны два числа — N и W(1  N  300;1  W  10000). Во второй строке N чисел — веса предметов и в третьей строке N чисел – стоимости предметов. Все числа не превышают 30000.

Выходные данные:

Выведите в первой строке искомую максимальную стоимость, а в последующих строках номер взятого предмета и количество.

Пример:

Input.txt	Output.txt
6 45 7 10 15 20 27 34 4 7 11 12 16 27	34 2 1 6 1
4 6 2 3 1 4 50 90 30 140	200 3 2 4 1

program rukzak2;

Const MaxN=100;

MaxW=100;

Var a,b:Array [0..MaxN,0..MaxW] Of Word; в массиве b храним количество

взятых предметов каждого вида

c,v:Array [1..MaxW] Of Longint;

i,j,n,w:Integer;

Procedure Init;

Begin

assign(input,'input.txt');

reset(input);

assign(output,'output.txt');

rewrite(output);

read(n,w); считываем количество видов предметов и

вместимость рюкзака

for i:=1 to n do read(v[i]); считываем веса

for i:=1 to n do read(c[i]); считываем стоимости

End;

Procedure Solve;

Var k,i,j:Integer;

Begin

fillchar(b,sizeof(b),0);

For i:=1 To N Do цикл по видам предметов

For j:=0 To W Do цикл по набранному весу

For k:=0 To j Div v[i] Do цикл по количеству предметов каждого вида

If j-k*v[i]<0 если К предметов вида i взять нельзя

Then

a[i,j]:=a[i-1,j] сохраняем предыдущий результат

else

if k*c[i]+a[i-1,j-k*v[i]]>a[i-1,j] сравниваем новый результат со старым

then

begin

a[i,j]:=k*c[i]+a[i-1,j-k*v[i]]; сохраняем лучший результат и

b[i,j]:=k; количество взятых предметов i-го вида

end

else

a[i,j]:=a[i-1,j]; сохраняем лучший результат

end;

Procedure OutWay(i,j:integer); выводим наибольшую стоимость и в кажой

из n следующих N строк номер предмета и его количество

Begin

If i=0

Then Exit

Else Begin

if a[i,j]=a[i-1,j]

then outway1(i-1,j)

else

begin

outway1(i-1,j-b[i,j]*v[i]);

writeln(i,' ',b[i,j]); выводим результат на подъеме из рекурсии

end;

End;

End;

Begin

Init;

Solve;

writeln(a[n,w]);

outway(n,w);

End.

динампрогрзадачи