0 / 0 / 0
Регистрация: 10.03.2013
Сообщений: 18
1

Задача "Движение по клеткам таблицы" (Динамическое программирование)

25.05.2015, 12:16. Показов 1943. Ответов 8
Метки нет (Все метки)

Хотел узнать, может у кого-нибудь в архивах есть подобная задача, которую можно будет использовать как шаблон к моей.
Есть таблица NxM, начальное положение человека и конечное положение человека в клетках этой таблицы. Таблица забита рандомными натуральными числами. Все эти данные берутся из ini-файла.
Человек может двигаться либо вправо, либо вверх. Нужно посчитать максимальную сумму элементов, проходя через которые человек доберется из начального положения в конечное.

Заранее спасибо за любую помощь!

P.S: Теорию ДП уже прочитал, проблема больше в реализации на С++
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.05.2015, 12:16
Ответы с готовыми решениями:

Динамическое программирование, задача "Уменьшение числа"
Имеется натуральное число N (1 <= N <= 106). За один ход с ним можно произвести следующие действия:...

Динамическое программирование игры "Ним"
Игра Ним с одной кучей камней и с инвертированными правилами (взявший последний камень...

Динамическое программирование задача "Калькулятор с восстановлением ответа" (Pascal ABC)
Всем привет. Пишу с проблемой о принятии моей задачи тестирующей программой. Сама задача: Имеется...

Нужна задача для курсовой "Динамическое программирование. Метод обратной прогонки"
Для моей курсовой работы нужно реализовать алгоритм в VBA по теме: "Динамическое программирование....

8
2548 / 1207 / 358
Регистрация: 30.11.2013
Сообщений: 3,826
25.05.2015, 12:19 2
ну решением в лоб будет рекурсия с массивом графов и суммой.
0
0 / 0 / 0
Регистрация: 10.03.2013
Сообщений: 18
25.05.2015, 12:22  [ТС] 3
Спасибо за ответ. Нужен именно шаблон, максимально приближенный к задаче, в дальнейшей реализации постараюсь справиться сам
0
Dimension
588 / 456 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
25.05.2015, 12:32 4
для начала заполните границы динамики,затем просто идите по таблице и суммируйте к динамике максимальный из элементов правой и верхней клетки динамики + элемент таблицы в котором находитесь
если есть куда сдать задачу в онлайн на проверку то киньте мб полный код напишу
0
0 / 0 / 0
Регистрация: 10.03.2013
Сообщений: 18
25.05.2015, 12:44  [ТС] 5
Я думаю решение таким методом будет не совсем то, что мне нужно. Все таки динамическое программирование не подразумевает решать задачу "перебором" (дело еще и в том, что работать придется с большими таблицами: 30+ столбцов и 30+ строк)
Если не удобно сюда код выкладывать, можете вк написать (скинул в лс)

Добавлено через 14 секунд
Dimension,
0
Dimension
588 / 456 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
25.05.2015, 12:53 6
мой метод это и есть двумерное дп
0
0 / 0 / 0
Регистрация: 10.03.2013
Сообщений: 18
25.05.2015, 12:59  [ТС] 7
Dimension, можете ваши наброски отправить?
0
Dimension
588 / 456 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
25.05.2015, 13:22 8
Лучший ответ Сообщение было отмечено bubliq как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int a[123][123], d[123][123];
int main(){
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            a[i][j]=rand() % ??
    int x,x1, y,y1;
    cin >> x >> y >> x1 >> y1;
    d[x1][y1] = a[x1][y1];
    for (int i = 1; i < n; i++)
        d[i][0] = d[i-1][0] + a[i][0];
    for (int i = 1; i < m; i++)
        d[0][i] = d[0][i-1] + a[0][i];
    for (int i = x1; i < x; i++)
        for (int j = y1; j < y; j++)
            d[i][j] = max(d[i][j - 1], d[i - 1][j]) + a[i][j];
    cout << d[x - 1][y - 1];
    return 0;
}
Добавлено через 2 минуты
начальное положение x y конечное x1 y1 ,сама таблица которое рандомом заполняется этом массив a
1
0 / 0 / 0
Регистрация: 10.03.2013
Сообщений: 18
25.05.2015, 13:38  [ТС] 9
Dimension, Спасибо большое Вам! Буду разбираться
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.05.2015, 13:38
Помогаю со студенческими работами здесь

Задача "Игра", динамическое программирование
Задаётся натуральное число n. Двое играющих называют по очереди числа, меньшие 107, по следующим...

Есть ли в России ВУЗ с кафедрой "Программирование игр", а не "Прикладное программирование" или "Кибернетика"
Просто боюсь что слишком много лишнего будет, или все же нет? Где-то слышал что есть в Росии...

Изобразить стрелку и осуществить движение по клавишам "вверх", "вниз", "вправо", "влево"
Необходимо изобразить стрелку и осуществить движение по клавишам &quot;вверх&quot;, &quot;вниз&quot;, &quot;вправо&quot;, &quot;влево&quot;.

вывести записи из таблицы "Таблица1", в которых есть название1, но при этом столбец "Код" из таблицы "Таблица1" присутствует в значениях столбца "Комм
Помогите пожалуйста, решить такую задачку. Необходимо вывести записи из таблицы &quot;Таблица1&quot;, в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru