Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

Вернуться   Форум программистов > Технологии > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail


Ответ
 
Опции темы
Старый 22.08.2009, 14:18   #1
MAKEDON
The First Person!
Форумчанин
 
Аватар для MAKEDON
 
Регистрация: 07.08.2007
Сообщений: 228
Вопрос Динамическое программирование.

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

Цитата:
В прямоугольной таблице NxM (в каждой клетке которой записано
некоторое число) в начале игрок находится в левой верхней клетке.
За один ход ему разрешается перемещаться в соседнюю клетку
либо вправо, либо вниз (влево и вверх перемещаться запрещено).
При проходе через клетку с игрока берут столько у.е., какое число
записано в этой клетке (деньги берут также за первую
и последнюю клетки его пути).

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

Входные данные
Во входном файле задано два числа N и M - размеры таблицы (1≤N≤20,
1≤M≤20). Затем идет N строк по M чисел в каждой - размеры штрафов
в у.е. за прохождение через соответствующие клетки (числа от 0 до 100).

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

Пример входного файла
3 4
1 1 1 1
5 2 2 100
9 4 2 1

Пример выходного файла
8
Программа обычно делает то что вы ей сказали сделать, а не то что бы вы хотели, чтобы она сделала.
MAKEDON вне форума Ответить с цитированием
Старый 22.08.2009, 14:26   #2
Levsha100
Влюбленный в С++
Старожил Подтвердите свой е-майл
 
Аватар для Levsha100
 
Регистрация: 20.07.2008
Сообщений: 4,033
По умолчанию

Эта задача решается с помощью ориентированных графов.
//Только почему такое странное название темы? О_О
Смотри в корень!
use linux - be happy

Последний раз редактировалось Levsha100; 22.08.2009 в 14:31.
Levsha100 вне форума Ответить с цитированием
Старый 22.08.2009, 14:26   #3
Sazary
В тени
Старожил
 
Аватар для Sazary
 
Регистрация: 19.12.2008
Сообщений: 5,788
По умолчанию

Вот, недавно было такое: http://programmersforum.ru/showthread.php?t=60512
Вполне очевидно, чтобы что-то понять, необходимо книги читать.
Не нужно плодить бессмысленных тем. Вас Поиск избавит от многих проблем.

___________________________________ ___________________________________ _______
[=Правила форума=]_____[Поиск]_____[Литература по С++]____[Литература. Паскаль]
Sazary вне форума Ответить с цитированием
Старый 22.08.2009, 17:04   #4
Somebody
Участник клуба
 
Регистрация: 08.10.2007
Сообщений: 1,185
По умолчанию

Цитата:
Сообщение от Levsha100 Посмотреть сообщение
Эта задача решается с помощью ориентированных графов.
//Только почему такое странное название темы? О_О
Потому что динамическим программированием решается легче, чем графами. Вроде даже на школьной олимпиаде эта задача как-то была.
Somebody вне форума Ответить с цитированием
Старый 23.08.2009, 14:21   #5
MAKEDON
The First Person!
Форумчанин
 
Аватар для MAKEDON
 
Регистрация: 07.08.2007
Сообщений: 228
По умолчанию

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

Последний раз редактировалось MAKEDON; 23.08.2009 в 18:50.
MAKEDON вне форума Ответить с цитированием
Старый 24.08.2009, 12:04   #6
Somebody
Участник клуба
 
Регистрация: 08.10.2007
Сообщений: 1,185
По умолчанию

a[0][1] = 0;
for (int x = 2; x <= m; x++)
a[0][x] = numeric_limits<int>::max();
for (int y = 1; y <= n; y++)
{
a[y][0] = numeric_limits<int>::max();
for (int x = 1; x <= m; x++)
cin >> a[y][x];
}
for (int y = 1; y <= n; y++)
for (int x = 1; x <= m; x++)
a[y][x] += min(a[y - 1][x], a[y][x - 1]);
[/code]
Минимальная сумма, полученная по пути для клетки, - это число в этой клетке плюс минимум из суммы для клетки слева и клетки сверху. Почитай Википедию про динамическое программирование, запусти пошагово на примере и посмотри.
Somebody вне форума Ответить с цитированием
Старый 26.08.2009, 14:10   #7
megachuhancer
Форумчанин
 
Регистрация: 16.04.2009
Сообщений: 247
По умолчанию

Цитата:
Эта задача решается с помощью ориентированных графов.
//Только почему такое странное название темы? О_О
Неее, это задача именно на динамическое программирование.
Идея такая. Пусть мы сейчас вычисляем оптимальную характеристику для [i, j] клетки. Пусть нам уже известна оптимальная характеристика для клеток левее этой клетки в этой же строке(i-той) и для всех клеток в предыдущих строках(с номером < i). Тогда как мы можем попасть в клетку [i, j]? Из клеток [i - 1, j] и [i, j - 1]. Надо только учитывать что в клетки первой строки мы можем попасть только слева и в клетки первого столбца только сверху. Выбираем минимум и не забываем добавить стоимость прохождения через саму клетку. Вот исходник, правда работает с числами только от 0 до 9 в каждой клетке. Таковы были ограничения задачи, которую я решал. Но главное, чтобы логика работы была понятна, а там переделаешь как тебе надо. Например на Delphi или C++. Там правда есть ещё несколько технических моментов, обусловленных ограничениями задачи, которую я решал, и Turbo Pascal'я на котором я её тогда писал.
Эта программа правда рисует в ASCII оптимальный маршрут, вместо того, чтобы выводить необходимое число, но из неё можно взять кусок основной логики. А, да, и ещё во входном файле цифры матрицы надо записывать без пробелов.
Код:
program routeproblem;
{$r+,q+}
const
	from_up=10;
	from_left=11;
	initial=12;
	route=13;
var
	c:char;
	T:array[1..250,1..250]of byte;
	M2:array[1..250]of integer;
	n,i,j:integer;
begin
	assign(input,'route.in');
	assign(output,'route.out');
	reset(input);
	rewrite(output);
	readln(n);
	i:=0;
	while not ((i=n) and (j=n)) do begin
		inc(i);
		j:=0;
		while not eoln do begin
			read(c);
			inc(j);
			T[i,j]:=ord(c)-ord('0');
		end;
		readln;
	end;
	M2[1]:=T[1,1];
	T[1,1]:=initial;
	for i:=2 to n do begin
		M2[i]:=T[1,i]+M2[i-1];
		T[1,i]:=from_left;
	end;
	for i:=2 to n do begin
		M2[1]:=T[i,1]+M2[1];
		T[i,1]:=from_up;
		for j:=2 to n do begin
			if M2[j]<M2[j-1] then begin
				M2[j]:=M2[j]+T[i,j];
				T[i,j]:=from_up;
			end
			else begin
				M2[j]:=M2[j-1]+T[i,j];
				T[i,j]:=from_left;
			end;
		end;
	end;
	i:=n;
	j:=n;
	while not (T[i,j]=initial) do begin
		if T[i,j]=from_left then begin
			T[i,j]:=route;
			dec(j);
		end;
		if T[i,j]=from_up then begin
			T[i,j]:=route;
			dec(i);
		end;
	end;
	T[1,1]:=route;
	for i:=1 to n do begin
		for j:=1 to n do
			if T[i,j]=route
			then write('#')
			else write('-');
		writeln;
	end;
	close(input);
	close(output);
end.
----------------------------------------------------------------------------------------------------------------------------------
Ладно, короче Самому стало интересно, так что не поленился написать то, что тебе нужно.
Код:
#include <cstdio>
#include <algorithm>
using namespace std;
int a[30][30], n, m;
int main() {
   scanf(" %d %d", &n, &m);
   for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
         scanf(" %d", &a[i][j]);
   for(int i = 1; i < m; i++) a[0][i] += a[0][i - 1];
   for(int i = 1; i < n; i++) a[i][0] += a[i - 1][0];
   for(int i = 1; i < n; i++)
      for(int j = 1; j < m; j++)
         a[i][j] += min(a[i - 1][j], a[i][j - 1]);
   printf("%d", a[n - 1][m - 1]);
   return 0;
}
-----------------------------------------------------------------------------------------------------------------------------------
Цитата:
Объясните на примере этой задачи, как вообще они решаются.
Нуу... Это трудно объяснить кратко. Я ведь и сам не каждую задачу на динамическое программирование решу. Короче, основная идея в табличном методе решения задач. Первоначально по английски это называлось memorization или как-то в этом роде. То есть надо забить в память промежуточные результаты решения подзадач. То есть надо чётко представлять какую характеристику мы хотим максимизировать(минимизировать) и как она зависит от остальных. Если делать по науке, то надо сначала выразить нужную характеристику рекуррентно. А потом, если есть локальный максимум(минимум), надо его собственно и найти(по формуле, если так можно выразиться), а не перебирать все варианты. И вообще, что я взялся рассказывать... Действительно, Википедия лучше обо всём расскажет
-----------------------------------------------------------------------------------------------------------------------------------
Из литературы могу рекомендовать:
1) Кормен, Ривест, Лейзерсон, Штайн. Алгоритмы: построение и анализ
2) Ф.Меньшиков. Олимпиадные задачи по программированию.
Правда, вторая немного устарела, в том плане, что на олимпиадах сейчас задачки и покруче бывают.

Последний раз редактировалось megachuhancer; 26.08.2009 в 14:52.
megachuhancer вне форума Ответить с цитированием
Ответ

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Опции темы


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
динамическое программирование в Delphi Ира08 Помощь студентам 0 03.04.2009 18:07
Задача на динамическое программирование Римма1990 Помощь студентам 2 02.04.2009 23:11
Рекуррентные соотношения и динамическое программирование. DOOM514 Фриланс 3 08.01.2009 17:20
Динамическое MainMenu dr.Chas Общие вопросы Delphi 4 24.06.2008 20:33