Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.63
Kemsit
4 / 4 / 4
Регистрация: 07.06.2009
Сообщений: 62
#1

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

29.12.2009, 23:06. Просмотров 1172. Ответов 5
Метки нет (Все метки)

Усложнили задачу мне.... :
Дан массив A[N,M]. Необходимо найти максимальную сумму элементов прямоугольного подмассива по всем возможным прямоугольным подмассивам.
Нужно решить с помощью динамического программирования.
Помогите кто может! Спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.12.2009, 23:06
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Динамическое программирование (C++):

Динамическое программирование
народ помогите пожалуйста. есть задача Написать программу, позволяющую...

Динамическое программирование
Помогите решить задачу! Я что-то особо не соображу... 1.Написать программу,...

Динамическое программирование
очень нужна реализация(завтра дедлайн) Будем называть натуральное число...

ДП Динамическое программирование
ограничение времени на тест: 0.5 сек. ограничение памяти на тест: 65536 KB. ...

Динамическое программирование
Столкнулся с такой задачей. Есть 6 фигурок площадью 3. Нужно узнать,...

Динамическое программирование
Мячик прыгает по лестнице, состоящей из N ступенек, строго сверху вниз. За один...

5
LeBron23
10 / 10 / 4
Регистрация: 18.11.2009
Сообщений: 47
29.12.2009, 23:42 #2
Есть минимум 3 способа решать это динамикой. Выложу самый медленный, но самый простой для понимания (n^4, N*M*N*M в нашем случае, для матрицы 100*100 в секунду укладывается).
Для начала находим сумму всех елементов во всех подмасивах с левым верхним углом в (1;1). Это делается примерно так:
C++
1
2
3
4
5
6
for (i=1;i<=N;i++)
{for (j=1;j<=M;j++){
cin>>t;
ar[i][j]=ar[i-1][j-1]+v[i]+g[j]+t;
v[i]+=t;g[j]+=t;
;};}
Считываем массив и на ходу заполняем таблицу динамики. в ar[i][j] у нас будет сумма элементов в прямоугольнике с углами в начале и этой клетке. в v и g - дополнительная информация, сумма по столбцам и строкам. Если массив уже дан (как в Вашем условии) - все то же самое, ну только не считываем, а работаем с готовым массивом (будет обращение к A[i][j]).
После этого можем приступать к самому перебору. Будем перебирать по 2 противоположным углам:
C++
1
2
3
4
5
6
7
for (i=1;i<=N;i++)
{for (j=1;j<=M;j++){
for(q=1;q<=i;q++){
for (t=1;t<=j;t++){
if (ar[i][j]-ar[i][t-1]-ar[q-1][j]+ar[t-1][q-1]>ans)
{ans=ar[i][j]-ar[i][t-1]-ar[q-1][j]+ar[t-1][q-1];}
;};};};}
В результате в ans будет ответ на задачу.
Чтоб понять, откуда "формула"
C++
1
if (ar[i][j]-ar[i][t-1]-ar[q-1][j]+ar[t-1][q-1]>ans)
- нарисуйте прямоугольники на бумажке, словамидолго расписывать.
0
Kemsit
4 / 4 / 4
Регистрация: 07.06.2009
Сообщений: 62
29.12.2009, 23:45  [ТС] #3
Что такое t?
0
LeBron23
10 / 10 / 4
Регистрация: 18.11.2009
Сообщений: 47
29.12.2009, 23:53 #4
Если даны только размерности массива, но не дано его содержание (надо сгенерить рэндомно или считать с файла/клавы), то t - то, что было бы в массиве А на позиции [i][j] (у нас просто нету необходимости хранить начальный массив). Если уже дан заполненый массив (он "в памяти" самой программы), то вместо t пишем A[i][j]. Понятно, что считывать в таком случае не надо.
С формальностей - если можно учитывать нулевой (пустой, размером 0*0) подмассив, то вначале
ans=0, иначе - ans="большое по модулю отрицательное число" (число, которое гарантировано меньше самого большого из отрицательных чисел на входе). Просто во втором случае может быть, что весь массив из отрицательных чисел и нету ни одного прямоугольника с сумой 0 или больше.
1
Kemsit
4 / 4 / 4
Регистрация: 07.06.2009
Сообщений: 62
30.12.2009, 00:16  [ТС] #5
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
using namespace std;
 
int main ()
{
        int mass[256][256], v[256], g[256], n, m, k=0, ans=0;
    setlocale (LC_ALL, "Russian");
    cout<<"Введите количество строк матрицы: "<< endl;
    cin>>n;
    cout<<"Введите количество строк матрицы: "<< endl;
    cin>>m; 
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            cout<<"Введите "<<i<<" "<<j<<" -> ";
            cin>>mass[i][j];
        }
    }
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            v[i]+=mass[i][j];
        }
    }
    for (int j=0; j<m; j++)
    {
        for (int i=0; i<n; i++)
        {
            g[j]+=mass[i][j];
        }
    }
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            mass[i][j]=mass[i-1][j-1]+v[i]+g[j]+mass[i][j];
            v[i]+=mass[i][j];
            g[j]+=mass[i][j];
        }
    }
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            for(int q=1; q<=i; q++)
            {
                for (int t=1 ;t<=j ;t++)
                { 
                    if (mass[i][j]-mass[i][t-1]-mass[q-1][j]+mass[t-1][q-1]>-1000)
                    {
                        ans=mass[i][j]-mass[i][t-1]-mass[q-1][j]+mass[t-1][q-1];
                    }
                }
            }
        }
    }
    cout<<"Ответ "<<ans;
 
        system ("pause");
    return 0; 
}
Исправьте, пожалуйста, ошибку в этом коде. Вроде пытался реализовать ваш алгоритм.
0
LeBron23
10 / 10 / 4
Регистрация: 18.11.2009
Сообщений: 47
30.12.2009, 12:41 #6
Цитата Сообщение от Kemsit Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    
for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            v[i]+=mass[i][j];
        }
    }
    for (int j=0; j<m; j++)
    {
        for (int i=0; i<n; i++)
        {
            g[j]+=mass[i][j];
        }
    }
Исправьте, пожалуйста, ошибку в этом коде. Вроде пытался реализовать ваш алгоритм.
Начну с того, что в моем алгоритме и близко не было такого.
Посмотрите на первый кусок кода из поста от 00:42. Идея v и g в том, чтоб считать сумму элементов до текущего. У Вас же - простое просчитывание сумм столбцов/строк, которое в итоге даст неверные (вернее, итоговые вместо промежуточных) значения в этих 2 массивах, и, как результат, неверные значения в матрице динамики с суммами по прямоугольникам. Еще и после лишнего заполнения делаете нужное в основном цикле, которое в итоге "вдвойне лишнее". Первое заполнение массивов сум вертикалей и горизонталей - лишнее.
Есть еще пару "менее важных" замечаний. К примеру, я писал, как видно с моего кода, с индексацией с 1 (привычка с Паскаля). Сдесь это удобно, если массив с нулевого элемента начинается, то при обращении mass[i-1][j-1] как раз будет обращение к (0;0), если массив по умолчанию занулен, то "все будет в порядке", там ноль, который даже прописывать не надо. Как себя поведет Ваша прог - турдно предположить. С одной стороны, нету обращения к -1ому элементу, так как при 0 вообще в цикл прога не заходит (там на вложеных ведь с 1 цикла начинается). С другой стороны, если самое большое число - первое (например, в матрице
10 -1
-1 -1
ответом будет именно число с координатами (0;0), или же (1;1) в моей реализации), то прога тоже будет криво работать. Край матрицы просто не рассматривается.

C++
1
if (mass[i][j]-mass[i][t-1]-mass[q-1][j]+mass[t-1][q-1]>-1000)
Еще вот здесь вопрос, почему сравниваете с числом, а не с ответом? просто вначале пишем ans=-1000 и дальше вместо -1000 ставим ans. А то у Вас ответ меняется каждый раз, когда находим прямоугольник с суммой больше -1000, а не с суммой больше текущего "лучшего результата".
З.Ы.
Для понимания того, как работают v и g, придумал пример.
Если в матрице вида
1 1 1 1 2 0
1 1 1 1 2 0
3 3 3 3 4 0
0 0 0 0 0 0
Надо посчитать сумму в прямоугольнике от левого верхнего угла до клетки с числом 4, то берем сумму прямоугольника из 1, столбца из 2, строки из 3 и самого числа из 4. Если наперед заполнить массив сум для 2 и 3 по всей таблице, то в учет пойдет примерно такая таблица:
1 1 1 1 2 0
1 1 1 1 2 0
3 3 3 3 4 3
0 0 0 0 2 0
Это если очень упрощенно и для понимания. У нас появились лишние клетки с 2 и 3, которые за пределами прямоугольника, но уже нами посчитаны.
0
30.12.2009, 12:41
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.12.2009, 12:41
Привет! Вот еще темы с решениями:

Динамическое программирование
На расстоянии n шагов от магазина стоит А. Каждую минуту он выбирает куда...

Динамическое программирование
Задача: Есть n работников и n работ. Необходимо найти максимальную суммарную...

Динамическое программирование.
Помогите, пожалуйста, составить алгоритм по одному из ниже представленных...

динамическое программирование
Народ помогите плиз найти алгоритм решения следующей задачи. На посвящение в...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru