Форум программистов, компьютерный форум CyberForum.ru

Динамическое программирование. Рыцарь. - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ подскажите аналог конструкции pascal в c http://www.cyberforum.ru/cpp-beginners/thread221841.html
Начал изучать язык Си без плюсов. подскажите, пожалуйста, аналог такой конструкции pascal if a in then в языке Си
C++ очень надо к 6 часам очень гадо к 6 часам Класс n-мерных векторов Базовый класс (координаты начала и конца вектора Совет: реализовать дополнительный класс NPoint, содержащий в виде массива координаты n-мерных точек, а также количество координат - N) Конструкторы: по умолчанию, с параметрами и копирования. Деструктор. Функции: перегрузки операции сложения; Перегрузка операции вычитания; перегрузки операции... http://www.cyberforum.ru/cpp-beginners/thread221836.html
C++ Вычислить: y=1!+2!+3!+…+n! (n>0).
Вычислить: y=1!+2!+3!+…+n! (n>0). Всем плюсану!
Даны действительные числа А,В,С . Найти те из них которые не принадлежат заданному отрезку [0; 2]. C++
Даны действительные числа А,В,С . Найти те из них которые не принадлежат заданному отрезку . кто напишет правильно программу тому "+"
C++ Сохранение информации в файле и считывание из него http://www.cyberforum.ru/cpp-beginners/thread221828.html
В файле сохраняется информация о деятельности некоторых подразделений: наименование подразделения, количество сотрудников, прибыль, полученная за текущий квартал. Определить лучшее подразделение с учетом числа сотрудников.
C++ C++ Блок схема Всем доброго времени суток. Есть проблема, которую я сам решить не могу из-за того, что ничерта не понимаю. Суть ее в следующем, есть код программы, написанной в С++, к этой программе нужна блок схема. Парни, кто может, помогите плиз, ну прям очень надо. Из за этой схемы курсак сдать не могу. Заранее всем откликнувшимся огромное спасибо. #include <iostream> #include <string> #include <vector>... подробнее

Показать сообщение отдельно
tymrfik
 Аватар для tymrfik
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
28.12.2010, 16:33     Динамическое программирование. Рыцарь.
Необходимо написать три версии алгоритма для решения предложенной задачи.
• неэффективная, при помоши рекуррентного спуска.
• с использованием динамического программирования.
• модификация первой, основанная на механизме «запоминания».
Задание:
За долгую и верную службу Рыцарю позволено набрать сокровищ в сокровищнице своего сеньора. Сокровищница имеет форму прямоугольника, состоящего из отдельных "клеток" — прямоугольных комнат. В каждой комнате хранятся сокровища известной стоимости. Рыцарь может вынести сколько угодно сокровищ, но пройдя через сокровищницу только один раз. Он может начать с любой комнаты вдоль внешней северной стены сокровищницы (выбор комнаты — за рыцарем). На каждом шаге он может переходить в одну из трех "южно-соседних" комнат: южную, юго-восточную или юго-западную. Из комнат, граничащих с восточной или западной внешней стеной, возможны только два направления выхода. Закончить путь Рыцарь должен в любой из комнат на южной внешней стороне сокровищницы.
У Рыцаря есть план сокровищницы — прямоугольная таблица, в которой обозначены стоимости сокровищ каждой комнаты. Направлению с севера на юг соответствует направление сверху вниз на карте.
По заданной карте нужно найти один из допустимых путей, обеспечивающих наибольшую возможную сумму сокровищ.

Вход. Первая строка в тексте содержит два числа N и М, обозначающие "ширину" и "высоту", далее М строк по N неотрицательных целых чисел в каждой — стоимости сокровищ соответствующих комнат. Размеры сокровищницы не более чем 80x80 комнат.
Выход. В первой строке указывается номер (по порядку с запада на восток) комнаты северного ряда, из которой нужно начать движение, во второй — строка символов, означающих на¬правление очередного перехода (S — на юг, Е — на юго-восток, W — на юго-запад); в третьей — полученная максимально возможная суммарная стоимость. Если есть несколько путей с максимальной суммой, вывести любой из них.
Помогите хотя б советом.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 00:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru