Дискретный анализ ← ЛабораторныеЛабораторная работа №7

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

При помощи метода динамического программирования разработать алгоритм решения задачи, определяемой своим вариантом; оценить время выполнения алгоритма и объем затрачиваемой оперативной памяти. Перед выполнением задания необходимо обосновать применимость метода динамического программирования.

Разработать программу на языке C или C++, реализующую построенный алгоритм. Формат входных и выходных данных описан в варианте зададния.

Варианты

1. Хитрый рюкзак

У вас есть рюкзак, вместимостью m, а так же n предметов, у каждого из которых есть вес wi и стоимость ci. Необходимо выбрать такое подмножество I из них, чтобы:

  • Σi∈Iwi ≤ m
  • i∈Ici)*|I| является максимальной из всех возможных.

|I| – мощность множества I.

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

В первой строке заданы 1 ≤ n ≤ 100 и 1 ≤ m ≤ 5000. В последующих n строках через пробел заданы параметры предеметов: wi и ci.

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

В первой строке необходимо вывести одно число – максимальное значение i∈Ici)*|I|, а на второй – индексы предметов, входящих в ответ.

Пример

Входной файл Выходной файл
3 6
2 1
5 4
4 2
6
1 3

2. Пустой прямоугольник

Задан прямоугольник с высотой n и шириной m, состоящий из нулей и единиц. Найдите в нём прямоугольник наибольшой площади, состоящий из одних нулей.

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

В первой строке заданы 1 ≤ n ≤ 500 и 1 ≤ m ≤ 500. В следующих n строках записаны по m символов 0 или 1 - элементы прямоугольника.

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

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

Пример

Входной файл Выходной файл
4 5
01011
10001
01000
11011
4

3. Количество чисел

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

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

В первой строке строке задано 1 ≤ n ≤ 1018 и 1 ≤ m ≤ 105.

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

Необходимо вывести количество искомых чисел.

Пример

Входной файл Выходной файл
42 3
11

Пояснение

Искомые числа: {3, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39}.

4. Игра с числом

Имеется натуральное число n. За один ход с ним можно произвести следующие действия:

  • Вычесть единицу
  • Разделить на два
  • Разделить на три

При этом стоимость каждой операции - текущее значение n. Стоимость преобразования - суммарная стоимость всех операций в преобразовании. Вам необходимо с помощью последовательностей указанных операций преобразовать число n в единицу таким образом, чтобы стоимость преобразования была наименьшей. Делить можно только нацело.

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

В первой строке строке задано 2 ≤ n ≤ 107.

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

Выведите на первой строке искомую наименьшую стоимость. Во второй строке должна содержаться последовательность операций. Если было произведено деление на 2 или на 3, выведите /2 (или /3). Если же было вычитание, выведите -1. Все операции выводите разделяя пробелом.

Пример

Входной файл Выходной файл
82
202
-1 /3 /3 /3 /3

5. Обход матрицы

Задана матрица натуральных чисел A размерности n × m. Из текущей клетки можно перейти в любую из 3-х соседних, стоящих в строке с номером на единицу больше, при этом за каждый проход через клетку (i, j) взымается штраф Ai,j. Необходимо пройти из какой-нибудь клетки верхней строки до любой клетки нижней, набрав при проходе по клеткам минимальный штраф.

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

Первая строка входного файла содержит в себе пару чисел 2 ≤ n ≤ 1000 и 2 ≤ m ≤ 1000, затем следует n строк из m целых чисел.

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

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

Пример

Входной файл Выходной файл
  3 3
  3 1 2
  7 4 5
  8 6 3
  8
  (1,2) (2,2) (3,3)

6. Палиндромы

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

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

Задана одна строка S (|S| ≤ 100).

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

Необходимо вывести одно число – ответ на задачу. Гарантируется, что он ≤ 263 - 1.

Пример

Входной файл Выходной файл
  BAOBAB
  22