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

Значения gok[i] для каждого k - ого перехода приведены в таблице

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

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

1 2 3 4 5 6

Значения d k [ i ] для каждого k - ого перехода приведены в таблице

Значения go^k[i] для каждого k - ого перехода приведены в таблице:

номер перехода k	go^k[1]	go^k[2]	go^k[3]
0	0	0	1
1	0	1	0
2	1	0	1

Из третьего города за два дня можно перебраться или в первый город, или снова вернуться в третий. Поскольку e = 1, d = 2 и go^d[e] = go²[1] = 1, то Теобальдо может совершить путешествие.

Реализация. Определим максимально возможное число городов MAX = 101. В массиве m содержим матрицу смежности графа, в массивах go и go1 будем пересчитывать значения go^k[i].
#define MAX 101

int m[MAX][MAX], go[MAX], go1[MAX];

Для каждого теста читаем значения c и l, обнуляем используемые массивы.
while (scanf("%d %d",&c,&l), c + l > 0)

{

memset(m,0,sizeof(m));

memset(go,0,sizeof(go));

memset(go1,0,sizeof(go1));

Читаем информацию о дорогах между городами, строим матрицу смежности. Дороги двусторонние.
for(i = 0; i < l; i++)

{

scanf("%d %d",&a,&b);

m[a][b] = m[b][a] = 1;

}
Вводим данные о маршруте Теобальдо, устанавливаем go[s] = 1.

scanf("%d %d %d",&s,&e,&d);

go[s] = 1;

Для каждого k, 1  k  d, совершаем пересчет значений go^k[i]. Считаем, что go^k^{– 1}[i] находятся в массиве go, а go^k[i] кладем в массив go1. Затем копируем массив go1 в массив go и так повторяем процесс d раз.
for(i = 0; i < d; i++)

{

for(x = 1; x <= c; x++)

for(y = 1; y <= c; y++)

if (go[y] && m[y][x])

{

go1[x] = 1; break;}

memcpy(go,go1,sizeof(go));

memset(go1,0,sizeof(go1));

}
В зависимости от значения go[e] печатаем результат.
if (go[e]) printf("Yes, Teobaldo can travel.\n");

else printf("No, Teobaldo can not travel.\n");

}
7. Путешествующий торговец [Вальядолид, 10702]. Нумерацию городов буем начинать с 0 (для удобства программирования на Си). Обозначим через d^k[i] максимальную прибыль, которую может получить торговец, если после совершения k переходов закончит свой путь в городе i (0  i < C, города нумеруются от 0 до C - 1). Изначально d⁰[S] = 0 (нулевая прибыль), d⁰[i] = -1 (прибыль не определена) для i S. Массив fin[i] будет содержать 1, если Джин может завершить свой путь в городе i и 0 иначе. Матрица m[i, j] (0  i, j < C) будет содержать прибыль, которую можно получить при переходе из города i в j.

Торговец должен совершить T переходов. Для каждого перехода будем пересчитывать значения d[i]. На k - ом переходе в i - ый город можно попасть из j - ого города (0  j < C), при этом максимальная прибыль при достижении i - ого города составит

d^k[i] = (d^k^-1[j] + m[j, i])

Условие d^k^-1[j]  0 гарантирует, что из начального города S за k - 1 переходов можно добраться до города j.

Для нахождения результата следует найти максимальное значение среди d^T[i], для которых fin[i] = 1 (город i может быть финальным).

Пример. Рассмотрим тест, данный в условии задачи. Поскольку нумерацию городов будем вести с нуля, то начальным городом будет 0, а конечными – 1 или 2. Матрица стоимостей переходов имеет вид:

m =

Значения d^k[i] для каждого k - ого перехода приведены в таблице:

номер перехода k	d^k[0]	d^k[1]	d^k[2]
0	0	-1	-1
1	0	3	5
2	14	7	5

Ответом будет max(d²[1], d²[2]) = 7.

Реализация. Пока первая строка очередного теста не содержит четыре нуля, читаем входные данные. Заполняем значения массивов d, fin, m. При этом помним, что нумерация городов в тестах начинается с 1, а в массивах будем хранить их с 0.
while(scanf("%d %d %d %d\n",&c,&s,&e,&t), c + s + e + t > 0)

{

s--;

for(i = 0; i < c; i++) {d[i] = -1; fin[i] = 0;}

for(d[s] = i = 0; i < c; i++)

{

for(j = 0; j < c; j++)

scanf("%d",&m[i][j]);

scanf("\n");

}

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

scanf("%d",&j), fin[j-1] = 1;

scanf("\n\n");

Для каждого из T переходов динамически пересчитываем оптимальные значения прибыли d[i] по выше приведенной формуле. Используем вспомогательный массив d1[i] .
while (t > 0)

{

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

{

for(d1[i] = j = 0; j < c; j++)

{

if (d[j] == -1) continue;

if (d[j] + m[j][i] > d1[i]) d1[i] = d[j] + m[j][i];

}

memcpy(d,d1,sizeof(d1)); t--;

}
Ищем максимальное значение d[i], среди тех i, для которых fin[i] = 1. Выводим результат.

for(res = i = 0; i < c; i++)

if ((d[i] > res) && fin[i]) res = d[i];

printf("%d\n",res);

}
8. Трамваи в Барселоне [Вальядолид, 10767]. Построим формулу среднего времени для движения трамвая по одному интервалу. Пусть m – максимально возможная скорость трамвая в начале интервала, s – длина интервала, x – скорость трамвая на ней. Тогда среднее время движения равно

f(x) = +

Найдем скорость x, для которой это время минимально. Раскроим скобки и сгруппируем:

f(x) = + x -

Производная равна

f’(x) = +

Приравняем ее к нулю, и решим уравнение относительно x. Получим оптимальную скорость

x =

Пусть a[i, j] – время, за которое можно доехать с остановки P_i до конца маршрута при условии, что до этого было j поломок. Очевидно, что a[n, i] = 0. Обозначим через

T0 = a[i + 1, j] – оптимальное время, за которое можно доехать с P_i₊₁ до конца с j поломками,

T1 = a[i + 1, j + 1] – оптимальное время, за которое можно доехать с P_i₊₁ до конца с j + 1 поломками.

Тогда среднее время проезда от P_i до конца равно

f(x) = +

Приравниваем производную к нулю (решаем уравнение f’(x) = 0), вычисляем скорость x, для которой это время будет минимальным. Она равна

x =

При вычислении a[i, j] следует помнить, что до P_i было j поломок. Тогда максимально возможная скорость, которую трамвай может выбрать на S_i₊₁, равна m = M₀ - j. Если вычисленная оптимальная скорость x будет больше чем M₀ - j, то положить x = M₀ - j.

Оптимальное среднее время, за которое трамвай проедет весь путь, равно a[0, 0]. Вычисление значений массива a идет с конца (сначала вычисляется столбик a[n - 1, i] (0  i  n - 1), потом a[n - 2, i] (0  i  n - 2) и так далее до a[0, 0]). Каждое значение a[i, j] пересчитывается через a[i + 1, j] и a[i + 1, j + 1].

a[0, 0]	a[1, 0]	a[2, 0]	a[3, 0]	a[4, 0] = 0
	a[1, 1]	a[2, 1]	a[3, 1]	a[4, 1] = 0
		a[2, 2]	a[3, 2]	a[4, 2] = 0
			a[3, 3]	a[4, 3] = 0
				a[4, 4] = 0

Пример. Рассмотрим второй тест. Данные матрицы a вместе с оптимальными значениями скоростей x приведены в таблице:

a[0, 0] = 205.0303 x = 14.8723	a[1, 0] = 102.0 x = 15.0	a[2, 0] = 0
	a[1, 0] = 103.7245 x = 14.6969	a[2, 1] = 0
		a[2, 2] = 0