Динамическое программирование. лаба №6. Лабораторная работа 6 "Динамическое программирование" Выполнила студентка группы 21ист колотова Валерия Задание

• Название: Лабораторная работа 6 "Динамическое программирование" Выполнила студентка группы 21ист колотова Валерия Задание
• Анкор: Динамическое программирование
• Дата: 19.12.2022
• Размер: 92.49 Kb.
• Имя файла: лаба №6.docx
• Тип: Лабораторная работа; #852094

Алгоритмы и структуры данных

Лабораторная работа №6 “Динамическое программирование”

Выполнила студентка группы 21ИСТ

Колотова Валерия

1. 
   Задание:
   

а) Задача о рюкзаке

б) Задача о нахождении максимальной суммы в треугольнике

в) Алгоритм Нидлмана-Вунша

2. 
   Описание значимых переменных:
   
   1. 
      Задача о рюкзаке:
      

• 
  arr_w, arr_p – массивы, где хранятся вес и ценность предметов
  
• 
  A – матрица
  
• 
  k, s – переменные, где хранятся кол-во вещей и макс. вес
  

1. 
   Задача о нахождении максимальной суммы в треугольнике:
   

• 
  n – переменная для хранения размера матрицы
  
• 
  A, В – матрица дерева и матрица с суммами
  
• 
  max_ind - массив, где содержаться индексы столбцов, по которым мы идем
  
• 
  int max_el - массив с максимальными элементами
  

1. 
   Алгоритм Нидлмана-Вунша
   

• 
  A, W – матрица с закрашенными элементами и матрица совпадений
  
• 
  result- массив из символов, где храниться цепочка совпадений
  
• 
  k – переменная хранящая размер цепочки
  
• 
  word1, word2 – данные цепочк символов.
  
• 
  n1, n2 – переменные для размеров матрицы
  

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

• 
  - стандартная библиотека для поддержки файлового ввода/вывода данных встроенных типов
  
• 
  - библиотека, включающая набор функций для выполнения алгоритмических операций над другими последовательностями.
  

4. 
   Описание методов и функций:
   

• 
  “max ” – функция из библиотеки algorithm, выбирающая максимальное значение
  

5. 
   Значимые фрагменты кода:
   

Задача о рюкзаке:
#include
using namespace std;
//Задача о рюкзаке

int main()

{

setlocale(LC_ALL, "Rus");

const int k = 5; //Количество вещей

int s = 15; //Максимальный вес
int arr_w[5] = { 6, 4, 3, 2, 5 }; //Массив с весами

int arr_p[5] = { 5, 3, 1, 3, 6 }; //Массив с приоритетом

int** A;

A = new int* [k + 1];

for (int i = 0; i < k + 1; i++)

{

A[i] = new int[s + 1];
}

for (int i = 0; i < s + 1 ; i++) //Заполняем первую строчку нулями

{

A[0][i] = 0;

}

for (int i = 1; i < k + 1; i++) //Заполняем первый столбец нулями

{

A[i][0] = 0;

}

for (int n = 1; n < k + 1; n++) //Цикл для заполнения матрицы по формуле

{

for (int m = 1; m < s + 1; m++)

{

if (m - arr_w[n - 1] >= 0) //проверка в случае, если индекс < 0, т. к. мы можем выйти за пределы матрицы

{

A[n][m] = max(A[n - 1][m], A[n - 1][m - arr_w[n - 1]] + arr_p[n - 1]);

}

else

{

A[n][m] = A[n - 1][m];

}

}

}

int i = k, j = s;
cout << "Предметы: ";

while (i != 0)

{

if (A[i][j] == A[i - 1][j])

{

while (A[i][j] == A[i - 1][j])

i--;

}

else

{

cout << i << " ";

j = j - arr_w[i - 1];

i--;

}

}

cout << endl;

for (int n = 0; n < k + 1; n++)

{

for (int m = 0; m < s + 1; m++)

cout << A[n][m] << "\t";

cout << endl;

}
cout << "Ответ: " << A[k][s];

}

Задача о нахождении максимальной суммы в треугольнике:

#include

#include

using namespace std;
void main()

{

setlocale(LC_ALL, "Rus");

int const n = 5; //Размер матрицы

int A[n][n] = //Задаем матрицу с деревом

{

{7, 0, 0, 0, 0},

{3, 8, 0, 0, 0},

{8, 1, 0, 0, 0},

{2, 7, 4, 4, 0},

{4, 2, 5, 6, 5}

};
int B[n][n + 1]; //Обьявление второй матрицы, содержащей сумму путей
for (int i = 0; i < n; i++) //Предварительно заполняем первый столбец матрицы с суммами 0-ми

{

B[i][0] = 0;

}

for (int i = 0; i < n; i++) //Остальные элементы матрицы с суммами приравниваем к элементам матрицы с деревом

{

for (int j = 1; j < n + 1; j++)

{

B[i][j] = A[i][j - 1];

}

}

for (int i = 1; i < n; i++) //Заполняем матрицу с суммами, используя формулу

{

for (int j = 1; j <= n; j++)

{

B[i][j] = B[i][j] + max(B[i - 1][j - 1], B[i - 1][j]);

}

}
int max_ind[n]; //Массив, где будут содержаться индексы столбцов, по которым мы идем
int max, in = 0; //Переменная max, которая будет приравниваться к максимальному значению

int max_el[n]; //Массив с максимальными элементами

for (int i = 0; i < n; i++)

{

max = B[i][0];

for (int j = 0; j < n; j++)

{

if (B[i][j] > max)

{

max = B[i][j];

max_ind[i] = j;

}

}

max_el[in] = max; //Массив с максимальными элементами, он заполняется на каждой итерации

in++; //Увеличение индекса на 1, так как на следующей итерации мы должны перейти на следующий эл-т

}

for (int i = 0; i < n; i++) //Вывод матрицы

{

for (int j = 0; j < n + 1; j++)

cout << B[i][j] << '\t';

cout << endl;

}
cout << "Путь: " << endl; //Вывод столбцов по которым мы идем

for (int i = 0; i < in; i++)

cout << max_ind[i] << " ";

}

Алгоритм Нидлмана-Вунша:

#include
using namespace std;
void main()

{

setlocale(LC_ALL, "Rus");

const char* word1 = "AGGCATTA";

const char* word2 = "GCCTAGA";
int n1 = 8;

int n2 = 7;
//A - матрица закрашивания

bool** A;

A = new bool* [n1];

for (int i = 0; i < n1; i++)

{

A[i] = new bool[n2];
for (int j = 0; j < n2; j++)

{

if (word1[i] == word2[j])

A[i][j] = 1;

else

A[i][j] = 0;

}

}

cout << "Матрица закрашивания:" << endl;

for (int i = 0; i < n1; i++)

{

for (int j = 0; j < n2; j++)

{

cout << A[i][j] << '\t';
}

cout << endl;

}

//W - матрица совпадений

int** W = new int* [n1];

for (int i = 0; i < n1; i++)

{

W[i] = new int[n2];

}

bool f = false;

for (int i = 0; i < n2; i++)

{

if (A[0][i] == 1)

{

f = true;

}

if (f)

W[0][i] = 1;

else

W[0][i] = 0;

}

f = false;

for (int i = 0; i < n1; i++)

{

if (A[i][0] == 1)

{

f = true;

}

if (f)

W[i][0] = 1;

else

W[i][0] = 0;

}
for (int i = 1; i < n1; i++)

{

for (int j = 1; j < n2; j++)

{

if (A[i][j] == 1)

{

W[i][j] = W[i - 1][j - 1] + 1;

}

else

W[i][j] = max((W[i - 1][j]), (W[i][j - 1]));

}

}
cout << "Матрица совпадений:" << endl;

for (int i = 0; i < n1; i++)

{

for (int j = 0; j < n2; j++)

{

cout << W[i][j] << '\t';
}

cout << endl;

}
char* result = new char[W[n1 - 1][n2 - 1]];
int current = 0;

for (int i = n1 - 1; i > 0; i--)

{

for (int j = n2 - 1; j > 0; j--)

{

if (W[i][j] == W[i - 1][j - 1] + 1 && A[i][j] == 1 && W[i][j] != W[i - 1][j] && W[i][j] != W[i][j - 1] && W[i][j] != current)

{

current = W[i][j];

result[W[i][j] - 1] = word1[i];

}

}

}

for (int i = 0; i < n1; i++)

{

if (W[i][0] == 1)

{

result[0] = word1[i];

break;

}

}

int k = 0;

for (int i = 0; i < W[n1 - 1][n2 - 1]; i++)

{

cout << result[i];

k++;

}

cout << endl;

cout << "Длина цепочки: " << k;

}

6. 
   Скриншоты выполнения программы:
   

З адача о рюкзаке:
Рис 1. – результат выполнения алгоритма решающего задачу о рюкзаке

Задача о нахождении максимальной суммы в треугольнике:



Рис 2. – результат выполнения алгоритма решающего задачу о максимальной сумме в треугольнике

А лгоритм Нидлмана-Вунша:
Рис 3. – результат выполнения программы, реализующей алгоритм Нидлмана-Вунша