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

Пример. Сумму s = 20 можно выдать 4 способами

жүктеу/скачать 0.53 Mb.

бет	2/6
Дата	19.07.2016
өлшемі	0.53 Mb.
	#208895
түрі	Решение

1 2 3 4 5 6

4. Оптимальное умножение матриц [Вальядолид, 348].
Пример .
Реализация .
5. Наибольшая общая подпоследовательность [Вальядолид, 10405].

Пример. Сумму s = 20 можно выдать 4 способами:

1) 20 2) 10 + 10 3) 10 + 5 + 5 4) 5 + 5 + 5 +5

	k \ n	0	5	10	15	20
начало	0	1	0	0	0	0
c = 5	1	1	1	1	1	1
c = 10	2	1	1	2	2	3
c = 20	3	1	1	2	2	4

Остальные номиналы не повлияют на результат для суммы в 20 центов.

Реализация. Ячейка mas[i] будет содержать количество способов, которыми можно выдать сумму i. Размер массива установим MAX = 30001. Номиналы монет (в центах) занесем в массив coins. Динамически пересчитываем массив mas для каждого номинала (всего 11 номиналов) согласно соотношению, приведенному в анализе алгоритма.

#include

#include
const int MAX = 30001;

double v;

int i,j,n;

long long mas[MAX];

int coins[11] = {5,10,20,50,100,200,500,1000,2000,5000,10000};
void main(void)

{

memset(mas,0,sizeof(mas)); mas[0] = 1;

for(i=0;i<11;i++)

{

for(j=coins[i];j

mas[j] += mas[j-coins[i]];

}
Читаем входные суммы v, преобразовываем их в целое число центов n и печатаем результат mas[n] в соответствии с требуемым форматом.

while(scanf("%lf",&v),v>0)

{

n = (int)(v*100+0.1);

printf("%6.2lf%17lld\n",v,mas[n]);

}

4. Оптимальное умножение матриц [Вальядолид, 348]. Обозначим через A_ij произведение матриц A_i * A_i₊₁ * … * A_j_-1 * A_j (1  i  j  n), через m[i, j] минимальное количество умножений, необходимое для вычисления A_ij. Стоимость вычисления всего произведения A₁_n будет храниться в m[1, n]. Значения m[i, i] = 0, поскольку A_ii = A_i и для его нахождения вычисления не нужны.

Количество столбцов матрицы A_i равно количеству строк матрицы A_i₊₁. Это значение хранится в p[i]. Количество строк матрицы А₁ находится в p[0], а количество столбцов A_n – в p[n].

Предположим, что при оптимальной расстановке скобок в произведении A_i * … * A_j последней операцией умножения будет (A_i * … * A_k ) * (A_k+1 * … * A_j). Значение m[i, j] равно сумме минимальной стоимости вычислений A_ik и A_k₊₁_j плюс стоимость умножения этих двух матриц:

m[i, j] = m[i, k] + m[k+1, j] + p[i-1] * p[k] * p[j]

При этом число k может принимать только j – i разных значений: i, i + 1, …, j – 1. Поскольку только одно из них является оптимальным, то необходимо перебрать все эти значения и выбрать наилучшее. Получим рекуррентную формулу:

m[i, j] =

Для запоминания оптимального умножения положим s[i, j] = k, если при оптимальном вычислении A_i * … * A_j последней операцией будет умножение A_i * … * A_k на A_k₊₁ * … * A_j.

Пример. Рассмотрим третий тест. Данные о размерах входных матриц сохраняются в массиве p:

Минимальная стоимость вычисления матриц A_ij хранится в ячейках массива m[i, j]:

i \ j	1	2	3	4	5	6
1	0	15750	7875	9375	11875	15125
2		0	2625	4375	7125	10500
3			0	750	2500	5375
4				0	1000	3500
5					0	5000
6						0

Соответствующие значения матрицы s:

i \ j	1	2	3	4	5	6
1	0	1	1	3	3	3
2	0	0	2	3	3	3
3	0	0	0	3	3	3
4	0	0	0	0	4	5
5					0	5
6						0

Для умножения шести входных матриц достаточно выполнить m[1,6] = 15125 операций умножения. Оптимальная последовательность умножений имеет вид:

A₁₆ = (s[1,6] = 3) = A₁₃ * A₄₆ =

(s[1,3] = 1, s[4,6] = 5) = (A₁₁ * A₂₃) * (A₄₅ * A₆₆) =

(s[2,3] = 2, s[4,5] = 4) = (A₁₁ * (A₂₂ * A₃₃ ) ) * ((A₄₄ * A₅₅) * A₆₆) =

(A₁ * (A₂ * A₃ ) ) * ((A₄ * A₅) * A₆)

Реализация. Переменная INF обозначает число «бесконечность», MAX – 1 содержит максимально возможное число матриц в произведении. Объявим строковый массив Stroka, в котором храним числа от 0 до 10 в виде строк. Объявим массивы m, s, p, описанные выше. В переменной Answer будем накапливать результат.

#define INF 0x3F3F3F3F

#define MAX 11

string Stroka[11] = {"0","1","2","3","4","5","6","7","8","9","10"};

int m[MAX][MAX], s[MAX][MAX], p[MAX];

string Answer;

Функция Mult находит минимальное количество умножений, необходимое для вычисления A_ij = A_i * A_i₊₁ * … * A_j_-1 * A_j, которое сохраняем в ячейке m[i, j].
int Mult(int i, int j)

{

int k, temp;

if (m[i][j] == INF)

for (k = i; k <= j - 1; k++)

{

temp = Mult(i,k) + Mult(k+1,j) + p[i-1] * p[k] * p[j];

if (temp < m[i][j])

{

m[i][j] = temp; s[i][j] = k;

}

return m[i][j];

}
Функция Print(i, j) выводит оптимальное произведение матриц A_i * A_i₊₁ * … * A_j_-1 * A_j согласно формату вывода.
string Print(int i, int j)

{

if (i == j) return "A" + Stroka[i];

return "(" + Print(i,s[i][j]) + " x " + Print(s[i][j]+1,j) + ")";

}
Основной цикл программы. Переменная cs содержит номер теста.

cs = 1;

while(scanf("%d",&n),n>0)

{
Присвоим всем ячейкам массива m значения «бесконечность».
memset(m,0x3F,sizeof(m));
Читаем размеры входных матриц, сохраняем их в массиве p. Положим m[i, i] = 0.
for(i = 1; i <= n; i++)

{

scanf("%d %d",&p[i-1],&p[i]); m[i][i] = 0;

}
Вычисляем результат – ищем оптимальное произведение матриц A₁ * A₂ * … * A_n_-1 * A_n.
Mult(1,n);
Выводим номер теста cs. Если n = 1, то перемножать нечего и следует вывести строку "(A1)". Иначе вызываем функцию Print(1,n), которая возвращает строку, содержащую последовательность оптимального произведения матриц.
printf("Case %d: ",cs++);

if (n == 1) Answer = "(A1)"; else Answer = Print(1,n);

Выводим результат – строку Answer.
printf("%s\n",Answer.c_str());

}
5. Наибольшая общая подпоследовательность [Вальядолид, 10405]. Пусть f(n, m) – длина максимальной общей подпоследовательности последовательностей x₁x₂…x_n и y₁y₂…y_m.

Если x_n  y_m, то f(n, m) = max( f(n, m - 1), f(n - 1, m) );

Если x_n = y_m, то f(n, m) = 1 + f(n - 1, m - 1);

Значения f(n, m) будем хранить в массиве c[0..1000, 0..1000], где c[0, i] = c[i, 0] = 0.

Каждая следующая строка массива с[i, j] вычисляется через предыдущую. Поэтому для нахождения ответа достаточно держать в памяти только две строки длины 1000.

жүктеу/скачать 0.53 Mb.

Достарыңызбен бөлісу:

1 2 3 4 5 6