Жадний алгоритм, це алгоритм, який на кожному кроці робить локально найкращий вибір в надії, що результат буде оптимальний



Скачати 290.62 Kb.
Дата конвертації09.04.2018
Розмір290.62 Kb.
ТипЗадача

Жадні алгоритми
Кожен програміст писав жадний алгоритм навіть не знаючи про це.
Жадний алгоритм, це алгоритм, який на кожному кроці робить локально найкращий вибір в надії, що результат буде оптимальний.
На кожному кроці алгоритму робиться, те що саме вигідно зробити в цей момент.
Мета:
Вважається, що жадібні алгоритми чимось похожі на динамічне програмування.
Відмінності: задача про рюкзак (з повторенням і неперервна).
Приклад. Маємо рюкзак об'єму 100. Та предмети різного об'єму та ціни.




Вартість

Об'єм

Питома вартість

1

120

60

2

2

80

50

8/5



Задача 1.

Написати програму, яка розмінює деяку суму грошей найменшим числом купюр.(Маємо купюри номіналом 1грн, 2грн, 5грн, 10грн, 20грн, 50грн, 100грн, 200грн, 500грн, 1000грн, 5000грн).



http://www.programmersforum.ru/showthread.php?t=117247
import java.util.*;

public class Bank {

public Bank() {

// TODO Auto-generated constructor stub

}

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner conin = new Scanner(System.in);

int Kupiury[]={5000, 1000, 500, 100, 50, 10, 5, 2, 1};

int x=conin.nextInt();

String s="";



int Ni,i=0;

while (x>=1){

Ni=x/Kupiury[i];



if (Ni>0){s=s+" "+Ni+"*"+Kupiury[i]+" ";}

x=x-Ni*Kupiury[i];

i++;

}

System.out.println(s);



}

}
В цьому алгоритмі, є одна проблема: якщо викинути 1грн купюри, то жадний алгоритм перестане дасть не вірний результат.


Задача 2.

Марсіани Міша і Маша вирішили разом підібрати подарунок на день народження Каті. Коли вони нарешті знайшли те, що хотіли, і упакували предмет в красиву коробку, потрібно було вирішити, як підписати подарунок. Друзі подумали, що кращим рішенням буде скласти загальний підпис так, щоб в ній як підрядки містилися їх імена.


Врахуйте, що на Марсі прийнято підписуватися повними іменами, а вони у марсіан можуть бути досить довгими.
Вхідні дані.

Вхідний файл INPUT.TXT містить два рядки, в яких записані повні імена друзів. Імена, як не дивно, складаються з букв латинського алфавіту, з яких тільки перша, - прописна. Довжина імен не перевершує 1000.


Вихідні дані.

У вихідний файл OUTPUT.TXT виведіть найкоротший рядок, в якому зустрічаються імена Миші і Маша одночасно. Букви, з яких імена починаються в цьому рядку треба зробити великими. Якщо існує декілька рішень, виведіть те, яке менше в алфавітному порядку.


Приклад



INPUT.TXT

OUTPUT.TXT

1

Misha
Masha

MashaMisha

2

Julya
Lyalya

JuLyalya

Розв'язок

В силу невеликих обмежень на довжину рядків ми можемо перебрати всілякі варіанти з'єднань, які можуть бути отримані з цих імен. Зробимо це таким чином: прибиратимемо по одному символу справа з першого імені і приписувати до нього друге, при цьому кожного разу перевірятимемо: чи починається рядок, що утворюється таким чином, з першого імені, якщо це так, то цей рядок задовольняє необхідній умові(закінчуватися вона буде другим іменем по побудові). При зустрічі чергового рядка, що починається і закінчується нашими іменами, порівнюватимемо її з раніше знайденим, на даний момент найкоротшим. Якщо поточний виявиться коротшим, то його слід запам'ятати. Після перебору усіх варіантів скорочення першого рядка слід поміняти рядки місцями, для чого зручно описати окрему функцію search(a, b), яка скорочуватиме перший рядок, доставляючи другу.
Слід так само відмітити, що в процесі порівняння треба перетворювати усі символи або у верхній, або в нижній регістр. На початку в якості найкоротшого рядка можна рахувати рядок, що складається з суми початкових імен, яка очевидно має необхідну властивість. Після завершення пошуку в якості відповіді просто залишиться вивести той рядок, в якому ми зберігали поточний найкоротший варіант.
Алгоритмическая реализация вышеописанной идеи:

String a,b,m,s; void search(a,b){ for i=len(a)..0{ s = a[1..i]+b; if ((len(lm)>len(ls) or len(lm)=len(ls) and m>s) and lower(a)=lower(left(s,len(a)))) m=s; } } read(a,b); m=a+b; search(a,b); search(b,a); write(m);

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

public class Signature {

static String search (String a,String b, String m) {

//toUpperCase toLowerCase

String s;

for (int i=a.length();i>0;i--){

s=a.substring(0,i)+b;

System.out.println(s+" "+m);

//if ((m.length()>=s.length()) && (m==s) && a.toLowerCase()==(s.substring(0,a.length())).toLowerCase()) m=s;



if ((m.length()>=s.length()) & a.toLowerCase()==(s.substring(0,a.length())).toLowerCase()) m=s;

System.out.println(a.toLowerCase()+"---"+(s.substring(0,a.length())).toLowerCase()+"===");

System.out.println(a.toLowerCase()==(s.substring(0,a.length())).toLowerCase());

System.out.println("julya"=="julya");

}

System.out.println("------"+m);



return m;

}

public static void main(String[] args) {

String a,b,Sign;

a="Julya";

b="Lyalya";

Sign=search(a,b,a+b);

System.out.println(Sign);

Sign=search(b,a,Sign);

System.out.println(Sign);

}
}


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

Динамічне програмування - це коли у нас

є одна велика задача, яку незрозуміло як розв'язувати,

і ми розбиваємо її на менші задачі, які теж

незрозуміло як розв'язувати.(с)А.Кумок
Динамічне програмування

Динамічним програмування називають метод, який дозволяє розв'язувати “переборні” задачі, спираючись на вже розв'язані підзадачі меншого розміру. При цьому необхідно, щоб всі розв'язки можна було заповнити в таблиці (тобто дані, обчислені один раз, не обчислюються знову).


Ідеї динамічного програмування сильно подібні на метод математичної індукції. Сформулюємо необхідні вимоги:
1. Всі розв'язки підзадач повинні зберігатись в таблиці.

2. Існує відомий розв'язок для задачі з малою розмірністю (аналогічно перевірці для мінімального параметра в методі математичної індукції).

3. Існує спосіб виразити розв'язок задачі через підзадачі (можливо, відмінний від початкової задачі) меншої розмірності. Це більше всього нагадує рекурентне співвідношення в математиці.
Якщо параметри підзадач «ідуть» в нескінченність» чи виникає кругова залежність то це значить, що метод динамічного програмування використати неможливо.
Задачі динамічного програмування діляться на два типи: оптимізація цільової функції та підрахунок кількості варіанту розв’язку.

В першому необхідно вибрати кращий серед всіх розв’язків, у другому – просумувати всі кількості розв’язків під задач.


У випадку якщо шукаємо розв’язок, часом буває необхідно підрахувати не тільки саму відповідь, але і відновити розв’язок повністю (записувати, які дії виконувались на кожному кроці).
1 Оптимізація цільової функції
До задач оптимізації цільової функції для заданого числа під задач відносяться ті задачі, в яких розв’язок можна знайти виходячи із того, що знаємо розв’язок декількох попередніх задач.
Задача 1. Хід конем

http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=269&chapterid=213


Шахова асоціація вирішила оснастити всіх своїх співробітників такими телефонними номерами, які б набиралися на кнопковому телефоні ходом коня. Наприклад, ходом коня набирається телефон 340-4927. При цьому телефонний номер не може починатися ні з цифри 0, ні з цифри 8.

Клавіатура телефону виглядає так:



7

8

9

4

5

6

1

2

3

 

0

 

Напишіть програму, що визначає кількість телефонних номерів довжини N, набираються ходом коня.

Вхідні дані. У вхідному файлі записано ціле число N(1 ≤ N ≤ 20).

Вихідні дані. Виведіть у вихідний файл шукану кількість телефонних номерів.

Приклад вхідних та вихідних даних



input.txt

output.txt

1

8

2

16

3

36

Нехай b[d][k] кількість номерів, які набираються ходом коня, які починаються з цифри d і складаються із k цифр. Тоді b[d][1]=1 для всіх d, а для любого d обчислюється через суму b[d][k-1] для k>1. Так наприклад, b[4][k] = b[0][k-1]+b[3][k-1]+b[9][k-1]. Збільшуючи k від 2 до n ми отримаємо значення b[d][n], сума яких (за мінусом b[0][n] і b[8][n]) і дасть відповідь на поставлену задачу.

Var

b:array[0..9,1..20] of integer;



k,n,s:integer;

begin


assign(input, 'input.txt');

reset(input);

readln(n);

close(input);

if n=1 then s:=8 else if n =2 then s:=16 else

if (n>2) and (n<=20) then

begin

b[0][2]:=2;



b[1][2]:=2;

b[2][2]:=2;

b[3][2]:=2;

b[4][2]:=3;

b[5][2]:=0;

b[6][2]:=3;

b[7][2]:=2;

b[8][2]:=2;

b[9][2]:=2;

for k:=3 to n do

begin

b[0][k]:=b[4][k-1]+b[6][k-1];



b[1][k]:=b[6][k-1]+b[8][k-1];

b[2][k]:=b[7][k-1]+b[9][k-1];

b[3][k]:=b[4][k-1]+b[8][k-1];

b[4][k]:=b[0][k-1]+b[3][k-1]+b[9][k-1];

b[6][k]:=b[0][k-1]+b[1][k-1]+b[7][k-1];

b[7][k]:=b[2][k-1]+b[6][k-1];

b[8][k]:=b[1][k-1]+b[3][k-1];

b[9][k]:=b[2][k-1]+b[4][k-1];

end;

for k:=0 to 9 do s:=s+b[k][n]; s:=s-b[0][n]-b[8][n];



end;

assign(output, 'output.txt');

rewrite(output); write(s);

close (output);

end.

Задача 2. Покупка білетів

Матеріали очного туру Московської олімпіади 2003/04 роки

http://olympiads.ru/moscow/2003/ochn/archive.shtml
За квитками на прем'єру нового мюзиклу вишикувалася черга з N людей, кожен з яких хоче купити 1 квиток. На усю чергу працювала тільки одна каса, тому продаж квитків йшов дуже повільно, приводячи "постояльців" черги у відчай. Найкмітливіші швидко помітили, що, як правило, декілька квитків в одні руки касир продає швидше, ніж коли ці ж квитки продаються по одному. Тому вони запропонували декільком людям, що підряд стоять, віддавати гроші першому з них, щоб він купив квитки на усіх.

Проте для боротьби із спекулянтами касир продавала не більше 3-х квитків в одні руки, тому домовитися таким чином між собою могли лише 2 або 3 людей, що стояли поряд.

Відомо, що на продаж i- ій людині з черги одного квитка касир витрачає Ai секунд, на продаж двох квитків - Bi секунд, трьох квитків - Ci секунд. Напишіть програму, яка підрахує мінімальний час, за який могли бути обслужені усі покупці.

Зверніть увагу, що квитки на групу людей, що об'єдналися, завжди купує перший з них. Також ніхто в цілях прискорення не купує зайвих квитків(тобто квитків, які нікому не потрібні).



Формат вхідних даних

У вхідному файлі записано спочатку число N - кількість покупців в черзі (1≤N≤5000). Далі йде N трійок натуральних чисел Ai, Bi, Ci. Кожне з цих чисел не перевищує 3600. Люди в черзі нумеруються починаючи від каси.



Формат вихідних даних

У вихідний файл виведіть одно число - мінімальний час в секундах, за який могли бути обслужені усі покупці.



Приклад

b.in

b.out

5

5 10 15


2 10 15

5 5 5


20 20 1

20 1 1


12

2

3 4 5


1 1 1

4

Розв’язок

Спробуємо знайти рішення задачі, поступово збільшуючи розмір черги. Нехай у нас в черзі стоїть всього одна людина. Оскільки кожній людині потрібний один і тільки один квиток(навіть якщо 2 або 3 квитки купити швидше), то відповіддю завдання буде число A1.

Тепер перейдемо до черги з 2 чоловік. Вони можуть купити квитки окремо, тоді час купівлі складе A1+ A2. Крім того, вони можуть об'єднатися і купити квитки разом, причому купити два квитки по умові завдання може тільки перша людина. З двох можливостей вибираємо таку, яка займе менше часу і запам'ятовуємо цей час в елементі D[2] спеціального масиву. Таким чином, D[2] - мінімальний час купівлі квитків чергою з 2 перших чоловік.

Додамо в чергу третю людину. Які варіанти є у нас? Якщо третя людина купує квиток самостійно, то перші два, очевидно, не залежать від нього. Тоді (увага!) ми вже вирішили це завдання! Ми тільки що знайшли мінімальний час купівлі квитків для черги з двох чоловік, воно зберігається в D[2]. Загальний час купівлі в цьому випадку складе D[2]+A3. Припустимо, друга і третя людина вирішать купити квитки разом. Відповіддю в цьому випадку буде B2 + A1(два квитки купує друга людина і перша людина купує квиток самостійно). Нарешті, домовитися зможуть і усі три людини. Тоді вони куплять квитки за C1 - саме стільки часу займе купівля трьох квитків у першої людини, що стоїть в черзі. Запишемо кращий варіант в D[3] - це буде мінімальний час купівлі квитків чергою з 3 перших чоловік.

Розглянемо усе вищесказане на прикладі з умови.

N=5


I

Ai

Bi

Ci

1

5

10

15

2

2

10

15

3

5

5

5

4

20

20

1

5

20

1

1

Заповнимо масив D початковими значеннями, D[1] = A1, інші елементи доки невідомі.

D[1]

D[2]

D[3]

D[4]

D[5]

5

???

???

???

???

Переходимо до з'ясування значення D[2]. Маємо, що при купівлі квитків окремо час складе A1 + A2 = 5 + 2 = 7, а при купівлі разом - 10. Отже, D[2]=min(7,10) =7.

D[1]

D[2]

D[3]

D[4]

D[5]

5

7

???

???

???

Додаємо в чергу третьої людини. Якщо він купує квиток окремо, то загальний час рівний D[2] + A3 = 7 + 5 = 12. Якщо другий і третій домовляється між собою, то загальний час буде

D[1] + B2 = 5 + 10 = 15. Нарешті, у разі спільної купівлі квитків трьома любителями мюзиклів, їм вдасться це зробити за час C1 = 15. Зрозуміло, вибираємо найшвидший варіант і в даному випадку D[3]=min(12,15,15) =12.


D[1]

D[2]

D[3]

D[4]

D[5]

5

7

12

???

???

Далі діятимемо абсолютно аналогічно. Додаємо до черги четвертої людини. Випишемо формулу для D[4].


D[4] = min ( D[3]+A4 , D[2] + B3 , D[1] + C2 )


Итак, D[4]=min(12+20, 7+5, 5+15)=min(32, 12, 20)=12

D[1]

D[2]

D[3]

D[4]

D[5]

5

7

12

12

???

Продовжуючи міркування аналогічно, в загальному вигляді отримуємо наступну формулу:




D[i] = min ( D[i-1]+Ai , D[i-2] + Bi-1 , D[i-3] + Ci-2 )

Відповіддю до завдання служитиме елемент масиву D[N]. У нашому випадку це D[5]. Дорозв’язуємо наш приклад: D[5]=min(6+20, 5+20, 7+5) =min(26, 25, 12) =12



D[1]

D[2]

D[3]

D[4]

D[5]

5

7

5

6

12 – відповідь задачі

Принцип, використовуваний при рішенні цієї задачі називається динамічним програмуванням. В даному випадку ми вирішуємо повну задачу, поступово розширюючи її розмірність і використовуючи рішення більше маленьких " підзадач".

Приведемо повне рішення задачі на мові Pascal.


import java.util.*;

import java.io.*;

public class kvitki {

static int min(int x, int y){

if (xreturn x;

else return y;

}

public static void main(String[] args) throws IOException {



int n;

FileReader fin = new FileReader("b.in");

// Write output to a file.

FileWriter fout = new FileWriter("b.out");

// Read and sum numbers.

Scanner src = new Scanner(fin);

n=src.nextInt();

int [] a=new int[n+1];

int [] b=new int[n+1];

int [] c=new int[n+1];

int [] d=new int[n+1];

for (int i=1; i<=n;i++){

a[i]=src.nextInt();



b[i]=src.nextInt();

c[i]=src.nextInt();

}

d[0]=0;


d[1]=a[1];

d[2]=min(a[1]+a[2],b[1]);



for (int i= 4;i<= n;i++){

d[i] = min( d[i-1] + a[i], min( d[i-2] + b[i-1], d[i-3] + c[i-2] ) );

}

System.out.println(d[n]);



fout.write(d[n]);

fin.close();

fout.close();

}

}



const

MaxN = 5000;

var

n : word; {число человек в очереди}



a, b, c : array [0 .. MaxN] of integer;

d : array [0 .. MaxN] of longint;

i : integer;
function min(a,b : longint) : longint;

begin


if aend;
begin

assign(input, 'b.in');

reset(input);

assign(output, 'b.out');

rewrite(output);


readln(n);

for i := 1 to n do

read(a[i], b[i], c[i]);
d[0] := 0;

d[1] := a[1];

d[2] := min(a[1]+a[2], b[1]);
for i := 3 to n do

d[i] := min( d[i-1] + a[i], min( d[i-2] + b[i-1], d[i-3] + c[i-2] ) );


writeln(d[n]);

close(input);

close(output);

end.




Задача_3._Задача_про_найбільшу_зростаючу_підпослідовність.'>Задача 3. Задача про найбільшу зростаючу підпослідовність.

Дано послідовність. Потрібно знайти довжину найбільшої зростаючої підпослідовності.

Вхідні дані. У першому рядку вхідного файлу записано число N- довжина послідовності (1≤N≤1000). У другому рядку записана сама послідовність (через пробіл). Числа послідовності – цілі числа, не перевищують 10000 по модулю.

Вихідні дані. У вихідний файл потрібно вивести найбільшу довжину зростаючої підпослідовності.



Приклад

b.in

b.out

6

3 29 5 5 28 6



3

Знайдемо довжину використовуючи динамічне програмування. Для цього створимо масив d[1..n], де d[i]- це довжина найдовшої зростаючої послідовності, що закінчується елементом і. Масив (він і є динаміка) будемо підраховувати поступово: спочатку d[1], потім d[2], і т.д. В кінці, коли це масив біде підрахований, відповіддю на задачу буде дорівнювати максимум в масиві d[].

Тобто, нехай поточний індекс – і, тобто ми хочемо підрахувати значення d[i], а всі попередні значення d[1]…d[i-1] вже підраховані. Тоді є можливих два варіанти:


  • або d[i]=1, тобто шукана послідовність складається тільки із числа a[i].

  • або d[i]>1. Тоді перед числом a[i] в шуканій послідовності стоїть якесь інше число. Давайте переберемо це число: це може бути любий елемент a[j] (j=0…i-1), але такий, що a[j]

Об’єднуючи два варіанта в один, отримуємо кінцевий алгоритм для обчислення d[i]:



Реалізація:

const nm=20;

Var


a:array[0..nm] of integer;

d:array[0..nm] of integer;

ans,n,i,j:integer;

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

begin

if a>b then max:=a else max:=b;



end;
begin

assign(input, 'input.txt');

reset(input);

readln(n);

for i:=1 to n do read(a[i]);

close(input);


for i:=1 to n do

begin


d[i]:=1;

for j:=1 to i do

if a[j]end;

ans:=d[1];

for i:=1 to n do ans:=max(ans,d[i]);
assign(output, 'output.txt');

rewrite(output); write(ans);

close (output);

end.
Начнем решать задачу с начала — будем искать ответ, начиная с первых членов данной последовательности. Для каждого номера i будем искать наибольшую возрастающую подпоследовательность, оканчивающуюся элементом в позиции i. Пусть исходная последовательность хранится в массиве A. В массиве L будем записывать длины максимальных подпоследовательностей, оканчивающихся текущим элементом. Пусть мы нашли все L[i] для 1 <= i <= k – 1. Теперь можно найти L[k] следующим образом. Просматриваем все элементы A[i] для 1 <= i < k – 1. Если


A[i] < A[k], то k-ый элемент может стать продолжением подпоследовательности, окончившейся элементом A[i]. Длина полученной подпоследовательности будет на 1 больше L[i]. Чтобы найти L[k], необходимо перебрать все i от 1 до k – 1:
L[k] = max(L[i]) + 1, где максимум берется по всем i таким, что A[i] < A[k] и
1 <= i < k.

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

Чтобы восстановить саму подпоследовательность, можно для каждого элемента также сохранять номер предыдущего выбранного элемента, например, в массив N.

Рассмотрим решение этой задачи на примере последовательности 2, 8, 5, 9, 12, 6. Поскольку до 2 нет ни одного элемента, то максимальная подпоследовательность содержит только один элемент — L[1] = 1, а перед ним нет ни одного — N[1] = 0. Далее,


2 < 8, поэтому 8 может стать продолжением последовательности с предыдущим элементом. Тогда L[2] = 2, N[2] = 1.

Меньше A[3] = 5 только элемент A[1] = 2, поэтому 5 может стать продолжением только одной подпоследовательности — той, которая содержит 2. Тогда


L[3] = L[1] + 1 = 2, N[3] = 1, так как 2 стоит в позиции с номером 1. Аналогично выполняем еще три шага алгоритма и получаем окончательный результат.

Теперь выбираем максимальный элемент в массиве L и по массиву N восстанавливаем саму подпоследовательность 2, 5, 9, 12.


2 Відновлення розв’язку

Найчастіше відновлення відбувається задом наперед, тобто від відповіді до початкової позиції і при необхідності перевертається. Для відновлення використовують або цикли, які переплигують деякі елементи, рухаючись від кінця до початку, або рекурсивні функції.



Задача

Дискретна задача про рюкзак
Задача. Представлення числа

Московская олимпиада по информатике 2005/06 г. Олимпиада 10-11 классов, 1 тур, 12 февраля 2006 года

Вчителька математики попросила школярів скласти арифметичний вираз, так щоб його значення дорівнювало числу N, і записати його в зошиті. У виразі можуть бути використані натуральні числа, не більші K, операції додавання і множення, а також дужки. Петя дуже не любить писати, і хоче придумати вираз, що містить якомога менше символів. Напишіть програму, яка допоможе йому в цьому.

Формат вхідних даних

У першому рядку вхідного файлу записано два натуральні числа: N(1≤N≤10000) - значення вираження і K(1≤K≤10000) - найбільше число, яке дозволяється використати у виразі.



Формат вихідних даних

У єдиному рядку вихідного файлу виведіть вираз з цим значенням, що записується найменшою можливою кількістю символів.

Якщо рішень декілька, виведіть будь-яке з них.

Примітка

При підрахунку довжини вираження враховуються усі символи: цифри, знаки операцій, дужки.



Примеры

c.in

c.out

Пояснение: длина получившегося выражения

7 3

3+1+3

5

15 20

15

2

176 1

(1+1+1+1)*(1+1+1+1)*(1+1+(1+1+1)*(1+1+1))

41

Задача решается применением метода динамического программирования. Прежде чем перейти к описанию идеи решения, введем несколько определений. Будем называть выражение C выражением первого типа, если оно является числом от 1 до K или если последней операцией при его вычислении является сложение, то есть, C = A + B, где A и B - некоторые выражения.

Будем называть выражение C выражением второго типа, если оно является числом от одного до K или если последней операцией при его подсчете является умножение, то есть, C = A * B, где A и B - некоторые выражения. Например, (2+3*4)+5*7 - выражение первого типа, (2+3)*(3+2) - выражение второго типа, 1 - выражение, относящееся как к первому, так и ко второму типу.

Теперь обсудим идею решения. Пусть a[1,m] равно наименьшей длине выражения первого типа, значение которого равно m; a[2,m] равно наименьшей длине выражения второго типа, значение которого равно m. Легко видеть, что при m <= K значения a[1,m] и a[2,m] равны длине числа m. Пусть теперь m > K, и у нас уже вычислены все значения a[1,1], :, a[1,m-1], a[2,1], :, a[2,m-1].

Сначала вычислим a[1,m]. Поскольку соответствующее выражение представимо в виде C=A+B, нам достаточно перебрать все возможные значения и типы выражений A и B и выбрать оптимальную комбинацию. Иными словами, a[1,m]=min(a[i1,t]+a[i2,m-t]+1), где i1, i2 - 1 или 2, а t <= m/2 (можно считать, что значение A меньше или равно m/2, иначе A и B можно поменять местами). В переменных how[1,m][1], how[1,m][2], how[1,m][3] будем хранить те значения i1, t, i2 соответственно, при которых достигается минимальное значение.
Теперь вычислим a[2,m]. Cоответствующее выражение представимо в виде A*B, где A и B - либо выражения второго типа, либо выражения первого типа, взятые в скобки (либо какая-то их комбинация). Будем считать, что значение A меньше или равно , иначе поменяем местами A и B. Таким образом, a[2,m]=min(a[i1,t]+a[i2,m/t]+1+2*(4-i1-i2)), где i1, i2 - 1или 2, а t <= sqrt(2) и m делится на t.

Замечание. Число 4-i1-i2 равно количеству выражений первого типа среди A и B, а значит, равно количеству пар скобок, которое придется добавить.


В переменных how[2,m][1], how[2,m][2], how[2,m][3] будем хранить те значения i1, t, i2 соответственно, при которых достигается минимум.

Теперь мы умеем вычислять значения a[1,1], ..., a[1,N], a[2,1], ..., a[2,N]. Естественно, что искомое выражение является выражением первого или второго типов, поэтому его длина равна min(a[1,N], a[2,N]). Осталось только научиться его выводить. Для этого напишем рекурсивную процедуру Save(last, n), которая будет выписывать выражение типа last, значением которого является n. Во-первых, если n<=K, то нужно просто вывести число cur. Иначе нужно посмотреть на значение last.

Если last=1 (то есть выражение имеет вид A+B), то сначала выпишем первое слагаемое - Save(how[last,n][1],how[last,n][2]) - затем поставим знак '+' и выпишем второе слагаемое - Save(how[last,n][3],n-how[last,n][2]).

Если last=2 (то есть, имеем дело с произведенем), то нужно действовать аналогично случаю last=1, но при этом не забыть, что если какой-то из множителей первого типа, то его надо окружить скобками.

Количество операций, выполняемых алгоритмом, пропорционально N2 что удовлетворяет указанным в условии задачи ограничениям.
Приведем теперь полный текст решения с подробными комментариями:
const

MaxN=10*1000;

var

N,K:LongInt;



a:array [1..2,1..MaxN] of LongInt;

how:array [1..2,1..MaxN,1..3] of LongInt;

m,i1,i2,t:LongInt;

function CountOfDigits(a:LongInt):byte;

//подсчитывает количество цифр в числе а

var


res:LongInt;

begin


res:=0;

while a>0 do begin

a:=a div 10;

//каждое деление на 10 уменьшает количество цифр на одну

inc(res);

end;


CountOfDigits:=res;

end;


procedure Save(last,n:LongInt);

//тип выражения и его значение

begin

if (n<=K) and (a[last,n]=CountOfDigits(n)) then



write(n)

//если n<=K, просто выводим n

else if last=1 then begin

//имеем дело с суммой

Save(how[last,n][1],how[last,n][2]);

//выводим первое слагаемое

write('+');

Save(how[last,n][3],n-how[last,n][2]);

//выводим второе слагаемое

end else if last=2 then begin

//имеем дело с произведением

if how[last,n][1]=1 then write('(');

Save(how[last,n][1],how[last,n][2]);

//выводим первый множитель

if how[last,n][1]=1 then write(')');

//если он первого типа, то окажется в скобках

write('*');

if how[last,n][3]=1 then write('(');

//аналогично поступаем со вторым множителем

Save(how[last,n][3],n div how[last,n][2]);

if how[last,n][3]=1 then write(')');

end;


end;

Begin


read(N,K);

for m:=1 to K do begin

//случай m<=K

a[1,m]:=CountOfDigits(m);

a[2,m]:=CountOfDigits(m);

end;


for m:=K+1 to N do begin

//случай K < m <= N

// считаем a[1,m] и how[1,m], перебирая i1, i2, t, ...

a[1,m]:=MaxLongInt;

//начальное значение

for t:=1 to (m div 2) do

for i1:=1 to 2 do

for i2:=1 to 2 do

if a[i1,t]+a[i2,m-t]+1

a[1,m]:=a[i1,t]+a[i2,m-t]+1;

how[1,m][1]:=i1;

how[1,m][2]:=t;

how[1,m][3]:=i2;

end;


// считаем a[2,m] и how[2,m], перебирая i1, i2, t, ...

a[2,m]:=MaxLongInt;

//начальное значение
for t:=1 to trunc(sqrt(m)) do if m mod t=0 then

for i1:=1 to 2 do

for i2:=1 to 2 do

if a[i1,t]+a[i2,m div t]+1+2*(4-i1-i2)

a[2,m]:=a[i1,t]+a[i2,m div t]+1+2*(4-i1-i2);

how[2,m][1]:=i1;

how[2,m][2]:=t;

how[2,m][3]:=i2;

end;

end;


if a[1,N]

// выводим выражение наименьшей длины

Save(1,N)

else


Save(2,N);

End.


================================================================

{$apptype console}

{$q+,r+,n-,o+}
const cinfile = 'c.in';

coutfile = 'c.out';


const nmax = 10011;

inf = maxlongint shr 1;


type int = longint;
var n, k : int;

strong, weak : array[1..nmax] of int;

s_strong, s_weak : array[1..nmax] of string;
procedure solve;

var i, j, t : int;

begin

for i:=1 to k do begin



str(i, s_strong[i]);

strong[i]:=length(s_strong[i]);

weak[i]:=strong[i];

s_weak[i]:=s_strong[i];

end;

for i:=k + 1 to n do begin



strong[i]:=inf;

weak[i]:=inf;

for j:=1 to i shr 1 do begin

if weak[i] > weak[i - j] + 1 + weak[j] then begin

weak[i]:=weak[i - j] + 1 + weak[j];

s_weak[i]:=s_weak[i - j] + '+' + s_weak[j];

end;

end;
for j:=1 to i do



if sqr(j) > i then break else begin

t:=i div j;

if (j > 1) and (i = t * j) then begin

if strong[i] > strong[t] + 1 + strong[j] then begin

strong[i]:=strong[t] + 1 + strong[j];

s_strong[i]:=s_strong[t] + '*' + s_strong[j];

end;

end;


end;
if strong[i] < weak[i] then begin

weak[i]:=strong[i];

s_weak[i]:=s_strong[i];

end else


if weak[i] + 2 < strong[i] then begin

strong[i]:=weak[i] + 2;

s_strong[i]:='(' + s_weak[i] + ')';

end;


end;

end;
begin

assign(input, cinfile); reset(input);

assign(output, coutfile); rewrite(output);

fillchar(strong, sizeof(strong), 0);

fillchar(weak, sizeof(weak), 0);

read(n, k);

solve;


write(s_weak[n]);

close(input); close(output);

end.
3 Підрахунок числа відповідей

Задачі підрахунки числа відповідей практично не відрізняються від задач пошуку відповіді. Але замість функції, що вибирає оптимальний розв’язок, тут використовується додавання або множення, в залежності від реалізації. Необхідно відмітити, що в більшості такого роду задач для зберігання кількості варіантів потрібна довга арифметика.

Як приклад класична задача про числа Фібоначі. В математичних термінах ми отримаємо рекурентне співвідношення Fi=Fi-1+Fi-2 та F0=1, F1=1.

http://habrahabr.ru/post/113108/

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

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.

Последовательности

Классической задачей на последовательности является следующая.

Последовательность Фибоначчи Fn задается формулами: F1 = 1, F2 = 1,
Fn = Fn – 1 + Fn – 2 при n > 1. Необходимо найти Fn по номеру n.

Один из способов решения, который может показаться логичным и эффективным, — решение с помощью рекурсии:

int F(int n) {

if (n < 2) return 1;

else return F(n - 1) + F(n - 2);

}


Используя такую функцию, мы будем решать задачу «с конца» — будем шаг за шагом уменьшать n, пока не дойдем до известных значений.

Но как можно заметить, такая, казалось бы, простая программа уже при n = 40 работает заметно долго. Это связано с тем, что одни и те же промежуточные данные вычисляются по несколько раз — число операций нарастает с той же скоростью, с какой растут числа Фибоначчи — экспоненциально.

Один из выходов из данной ситуации — сохранение уже найденных промежуточных результатов с целью их повторного использования:

int F(int n) {

if (A[n] != -1) return A[n];

if (n < 2) return 1;

else {

A[n] = F(n - 1) + F(n - 2);



return A[n];

}

}


Приведенное решение является корректным и эффективным. Но для данной задачи применимо и более простое решение:

F[0] = 1;

F[1] = 1;

for (i = 2; i < n; i++) F[i] = F[i - 1] + F[i - 2];

Такое решение можно назвать решением «с начала» — мы первым делом заполняем известные значения, затем находим первое неизвестное значение (F3), потом следующее и т.д., пока не дойдем до нужного.

Именно такое решение и является классическим для динамического программирования: мы сначала решили все подзадачи (нашли все Fi для i < n), затем, зная решения подзадач, нашли ответ (Fn = Fn – 1 + Fn – 2, Fn – 1 и Fn – 2 уже найдены).

Одномерное динамическое программирование


Чтобы лучше понять суть динамического программирования, сначала более формально определим понятия задачи и подзадачи.

Пусть исходная задача заключается в нахождении некоторого числа T при исходных данных n1, n2, ..., nk. То есть мы можем говорить о функции T(n1, n2, ..., nk), значение которой и есть необходимый нам ответ. Тогда подзадачами будем считать задачи
T(i1, i2, ..., ik) при i1 < n1, i2 < n2, ..., ik < nk.

Далее мы будем о говорить об одномерном, двумерном и многомерном динамическом программировании при k = 1, k = 2, k > 2, соответственно.

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

Задача 1. Посчитать число последовательностей нулей и единиц длины n, в которых не встречаются две идущие подряд единицы.

При n < 32 полный перебор потребует нескольких секунд, а при n = 64 полный перебор не осуществим в принципе. Для решения задачи методом динамического программирования сведем исходную задачу к подзадачам.

При n = 1, n = 2 ответ очевиден. Допустим, что мы уже нашли Kn – 1, Kn – 2 — число таких последовательностей длины n – 1 и n – 2.

Посмотрим, какой может быть последовательность длины n. Если последний ее символ равен 0, то первые n – 1 — любая правильная последовательность длины


n – 1 (не важно, заканчивается она нулем или единицей — следом идет 0). Таких последовательностей всего Kn – 1. Если последний символ равен 1, то предпоследний символ обязательно должен быть равен 0 (иначе будет две единицы подряд), а первые
n – 2 символа — любая правильная последовательность длины n – 2, число таких последовательностей равно Kn – 2.

Таким образом, K1 = 2, K2 = 3, Kn = Kn – 1 + Kn – 2 при n > 2. То есть данная задача фактически сводится к нахождению чисел Фибоначчи.

Двумерное динамическое программирование

Классической задачей двумерного динамического программирования является задача о маршрутах на прямоугольном поле.


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

Приведем пару формулировок таких задач:



Задача 2. Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо или вниз. Посчитать, сколькими способами можно попасть из левой верхней клетки в правую нижнюю.

Задача 3. Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо, вниз или по диагонали вправо-вниз. В каждой клетке записано некоторое натуральное число. Необходимо попасть из верхней левой клетки в правую нижнюю. Вес маршрута вычисляется как сумма чисел со всех посещенных клеток. Необходимо найти маршрут с минимальным весом.

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

Рассмотрим более подробно задачу 2. В некоторую клетку с координатами (i,j) можно прийти только сверху или слева, то есть из клеток с координатами (i – 1, j) и (i, j – 1):

Таким образом, для клетки (i, j) число маршрутов A[i][j] будет равно


A[i – 1][j] + A[i][j – 1], то есть задача сводится к двум подзадачам. В данной реализации используется два параметра — i и j — поэтому применительно к данной задаче мы говорим о двумерном динамическом программировании.

Теперь мы можем пройти последовательно по строкам (или по столбцам) массива A, находя число маршрутов для текущей клетки по приведенной выше формуле. Предварительно в A[0][0] необходимо поместить число 1.

В задаче 3 в клетку с координатами (i, j) мы можем попасть из клеток с координатами
(i – 1, j), (i, j – 1) и (i – 1, j – 1). Допустим, что для каждой из этих трех клеток мы уже нашли маршрут минимального веса, а сами веса поместили в W[i – 1][j], W[i][j – 1],
W[i – 1][j – 1]. Чтобы найти минимальный вес для (i, j), необходимо выбрать минимальный из весов W[i – 1][j], W[i][j – 1], W[i – 1][j – 1] и прибавить к нему число, записанное в текущей клетке:

W[i][j] = min(W[i–1][j], W[i][j – 1], W[i – 1][j – 1]) + A[i][j];

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

На следующем рисунке приведен пример исходных данных и одного из шагов алгоритма.



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

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

Задачи на подпоследовательности


Рассмотрим задачу о возрастающей подпоследовательности.



Задача 4. Дана последовательность целых чисел. Необходимо найти ее самую длинную строго возрастающую подпоследовательность.

Начнем решать задачу с начала — будем искать ответ, начиная с первых членов данной последовательности. Для каждого номера i будем искать наибольшую возрастающую подпоследовательность, оканчивающуюся элементом в позиции i. Пусть исходная последовательность хранится в массиве A. В массиве L будем записывать длины максимальных подпоследовательностей, оканчивающихся текущим элементом. Пусть мы нашли все L[i] для 1 <= i <= k – 1. Теперь можно найти L[k] следующим образом. Просматриваем все элементы A[i] для 1 <= i < k – 1. Если


A[i] < A[k], то k-ый элемент может стать продолжением подпоследовательности, окончившейся элементом A[i]. Длина полученной подпоследовательности будет на 1 больше L[i]. Чтобы найти L[k], необходимо перебрать все i от 1 до k – 1:
L[k] = max(L[i]) + 1, где максимум берется по всем i таким, что A[i] < A[k] и
1 <= i < k.

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

Чтобы восстановить саму подпоследовательность, можно для каждого элемента также сохранять номер предыдущего выбранного элемента, например, в массив N.

Рассмотрим решение этой задачи на примере последовательности 2, 8, 5, 9, 12, 6. Поскольку до 2 нет ни одного элемента, то максимальная подпоследовательность содержит только один элемент — L[1] = 1, а перед ним нет ни одного — N[1] = 0. Далее,


2 < 8, поэтому 8 может стать продолжением последовательности с предыдущим элементом. Тогда L[2] = 2, N[2] = 1.

Меньше A[3] = 5 только элемент A[1] = 2, поэтому 5 может стать продолжением только одной подпоследовательности — той, которая содержит 2. Тогда


L[3] = L[1] + 1 = 2, N[3] = 1, так как 2 стоит в позиции с номером 1. Аналогично выполняем еще три шага алгоритма и получаем окончательный результат.

Теперь выбираем максимальный элемент в массиве L и по массиву N восстанавливаем саму подпоследовательность 2, 5, 9, 12.

Еще одной классической задачей динамического программирования является задача о палиндромах.

Задача 5. Дана строка из заглавных букв латинского алфавита. Необходимо найти длину наибольшего палиндрома, который можно получить вычеркиванием некоторых букв из данной строки.

Обозначим данную строку через S, а ее символы — через S[i], 1 <= i <= n. Будем рассматривать возможные подстроки данной строки с i-го по j-ый символ, обозначим их через S(i, j). Длины максимальных палиндромов для подстрок будем записывать в квадратный массив L: L[i][j] — длина максимального палиндрома, который можно получить из подстроки S(i, j).

Начнем решать задачу с самых простых подстрок. Для строки из одного символа (то есть подстроки вида S(i, i)) ответ очевиден — ничего вычеркивать не надо, такая строка будет палиндромом. Для строки из двух символов S(i, i + 1) возможны два варианта: если символы равны, то мы имеем палиндром, ничего вычеркивать не надо. Если же символы не равны, то вычеркиваем любой.

Пусть теперь нам дана подстрока S(i, j). Если первый (S[i]) и последний (S[j]) символы подстроки не совпадают, то один из них точно нужно вычеркнуть. Тогда у нас останется подстрока S(i, j – 1) или S(i + 1, j) — то есть мы сведем задачу к подзадаче: L[i][j] = max(L[i][j – 1], L[i + 1][j]). Если же первый и последний символы равны, то мы можем оставить оба, но необходимо знать решение задачи S(i + 1, j – 1):


L[i][j] = L[i + 1][j – 1] + 2.

Рассмотрим решение на примере строки ABACCBA. Первым делом заполняем диагональ массива единицами, они будут соответствовать подстрокам S(i, i) из одного символа. Затем начинаем рассматривать подстроки длины два. Во всех подстроках, кроме S(4, 5), символы различны, поэтому в соответствующие ячейки запишем 1, а в L[4][5] — 2.

Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали, ведущей из левого верхнего угла в правый нижний. Для подстрок длины 3 получаются следующие значения: в подстроке ABA первая и последняя буквы равны, поэтому
L[1][3] = L[2][2] + 2. В остальных подстроках первая и последняя буквы различны.

BAC: L[2][4] = max(L[2][3], L[3][4]) = 1.


ACC: L[3][5] = max(L[3][4], L[4][5]) = 2.
CCB: L[4][6] = max(L[4][5], L[5][6]) = 2.
CBA: L[5][7] = max(L[5][6], L[6][7]) = 1.

Продолжая далее аналогичные рассуждения, заполним все ячейки под диагональю и в ячейке L[1][7] = 6 получим ответ.



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







Поділіться з Вашими друзьями:


База даних захищена авторським правом ©wishenko.org 2017
звернутися до адміністрації

    Головна сторінка