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

Динамическое программирование. Нахождение максимального пути при проходе по таблице. - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Одноразовый вывод повторяющихся значений http://www.cyberforum.ru/cpp-beginners/thread229558.html
Задача: Написать шаблонную функцию, котороая будет принимать массивы любого типа const int size=10; int mas={ 1, 2, 3, 4, 1, 2, 3, 4, 5, 6}; char mas={'!', '@', '!', '$', '%', '^', '$', '^', '^', ')'}; double mas={1.1, 2.2, 1.1, 3.3, 4.4, 5.5, 5.5, 3.3, 2.2, 9.9}; и выводила повторяющиеся значения(значение должно выводиться один раз) например:
C++ Найти ошибку При компиляции ошибок не выдаёт, но когда запускаю программу она вылетает #include "stdafx.h" #include <conio.h> #include <math.h> #include <string.h> void main() { http://www.cyberforum.ru/cpp-beginners/thread229557.html
C++ Динамическое программирование.Распределение алфавита по кнопкам мобильника.
Добрый день. Умные товарищи, помогите пожалуйста, прижало так прижало-экзамен на носу а для допуска надо задачу решить. Надеюсь на вашу помощь. Вот задача для С++: Существует следующий способ набора букв на мобильном телефоне. Клавише 2 сопоставлены буквы abc, клавише 3 def и т.д. При наборе текста одно нажатие на клавишу 2 порождает символ а, два подряд нажатия символ b, три подряд символ c;...
Упорядочить 5 чисел за 7 операций C++
Каждый частный придуманный мной алгоритм терпел крах. Если это попадание пальцем в небо, то, видимо, это мне не по силам. Упорядочить по невозрастанию 5 чисел за 7 операций сравнения. Может кто уже сталкивался с такой задачей. Заранее благодарен.
C++ Найти количество слов, начинающихся на гласные буквы http://www.cyberforum.ru/cpp-beginners/thread229539.html
Очень прошу помочь с задачей. Наверно, она не сложная, но для меня легче курсовую по английскому написать, чем задачу по программированию( помогите, пожалуйста: Дана строка – предложение на русском языке, слова которого разделены одним или несколькими пробелами, могут использоваться знаки препинания точка и запятая. Найти количество слов, начинающихся на гласные буквы
C++ как вставить строки ..пожалуйстаа^^ 1.Дана матрица размера M х N и целое число K (1 <= K <= M). Перед строкой матрицы с номером K вставить 3 строки из 1. 2.Дан целочисленный массив размера N. Удалить из массива все элементы, встречающиеся менее 2 раз, и вывести размер полученного массива и его содержимое. хоть убейте,элементарно после ввода-вывода матрицы застреваю на циклах,хоть и понимаю что именно нужно сделать и в какой... подробнее

Показать сообщение отдельно
Adriano_Che
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 6
16.01.2011, 13:43     Динамическое программирование. Нахождение максимального пути при проходе по таблице.
Всем добрый день. Задачу почти решил-не могу сделать один момент. Подскажите пожалуйста. Вот задача:

Прямоугольная таблица имеет М строк и N столбцов. Нужно пройти из левого верхнего угла таблицы в правый нижний, на каждом шаге перемещаясь на 1 клетку вправо или вниз.
"Хорошими" считаются не только пути с максимально возможной суммой, но и пути, сумма которых отличается от максимальной не более чем на К. Количество "хороших" путей гарантированно не больше 10.
Найти максимально возможную сумму и количество "хороших" путей.

Вход. Первая строка входного текста содержит три целых числа М (2<М<200), N (2<N<200) и K (0<K<200). Каждая из следующих М строк задает N чисел в соответствующих клетках.
Выход. Первая строка текста должна содержать максимально возможную сумму, вторая — количество маршрутов, сумма чисел которых отличается от максимальной не более чем на K.

Я нашёл максимальный путь, но не знаю как найти "хорошие" пути. Помогите пожалуйста. Вот код для нахождения максимального пути:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<stdio.h>
#include<conio.h>
using namespace std;
int main()
{
        int N, M, i, j, **a, **b;
        cin>>N>>M;
        a=new int*[M];
        b=new int*[M];
        for(i=0; i<M; i++)
        {
                a[i]=new int[N];
                b[i]=new int[N];
                for(j=0; j<N; j++)
                {
                        cin>>a[i][j];
                        b[i][j]=a[i][j];
                }
        }
        for (i=N-2;i>=0;i--)
            b[M-1][i]+=b[M-1][i+1];
        for(i=M-2; i>=0; i--)
        for(j=N-1; j>=0; j--)
        {
                int max=b[i+1][j];
                if(j<(N-1) && (b[i][j+1]>max))
                        max=b[i][j+1];
                b[i][j]+=max;
        }
        cout<<"max="<<b[0][0]<<endl;
        system("PAUSE");
        return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 15:07. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru