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

@Kemsit · Регистрация: 07.06.2009

Студворк — интернет-сервис помощи студентам

Усложнили задачу мне.... :
Дан массив A[N,M]. Необходимо найти максимальную сумму элементов прямоугольного подмассива по всем возможным прямоугольным подмассивам.
Нужно решить с помощью динамического программирования.
Помогите кто может! Спасибо.

@LeBron23 · 29.12.2009, 23:42

Есть минимум 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)

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

@Kemsit · 29.12.2009, 23:45 **[ТС]**

Что такое t?

@LeBron23 · 29.12.2009, 23:53

Если даны только размерности массива, но не дано его содержание (надо сгенерить рэндомно или считать с файла/клавы), то t - то, что было бы в массиве А на позиции [i][j] (у нас просто нету необходимости хранить начальный массив). Если уже дан заполненый массив (он "в памяти" самой программы), то вместо t пишем A[i][j]. Понятно, что считывать в таком случае не надо.
С формальностей - если можно учитывать нулевой (пустой, размером 0*0) подмассив, то вначале
ans=0, иначе - ans="большое по модулю отрицательное число" (число, которое гарантировано меньше самого большого из отрицательных чисел на входе). Просто во втором случае может быть, что весь массив из отрицательных чисел и нету ни одного прямоугольника с сумой 0 или больше.

@Kemsit · 30.12.2009, 00:16 **[ТС]**

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; 
}

Исправьте, пожалуйста, ошибку в этом коде. Вроде пытался реализовать ваш алгоритм.

@LeBron23 · 30.12.2009, 12:41

Сообщение от 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, которые за пределами прямоугольника, но уже нами посчитаны.

Новые блоги и статьи Все статьи Все блоги /
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Нашел на реддите интересную статью под названием «Кто-нибудь знает, где получить бесплатный компьютер или. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .

@Kemsit 5 / 5 / 0 Регистрация: 07.06.2009 Сообщений: 62

	Динамическое программирование 29.12.2009, 23:06. Показов 1992. Ответов 5 Метки нет (Все метки) Усложнили задачу мне.... : Дан массив A[N,M]. Необходимо найти максимальную сумму элементов прямоугольного подмассива по всем возможным прямоугольным подмассивам. Нужно решить с помощью динамического программирования. Помогите кто может! Спасибо. 0

@Kemsit 5 / 5 / 0 Регистрация: 07.06.2009 Сообщений: 62
	29.12.2009, 23:45 [ТС]
	Что такое t? 0

@LeBron23 10 / 10 / 4 Регистрация: 18.11.2009 Сообщений: 47
	29.12.2009, 23:53
	Если даны только размерности массива, но не дано его содержание (надо сгенерить рэндомно или считать с файла/клавы), то t - то, что было бы в массиве А на позиции [i][j] (у нас просто нету необходимости хранить начальный массив). Если уже дан заполненый массив (он "в памяти" самой программы), то вместо t пишем A[i][j]. Понятно, что считывать в таком случае не надо. С формальностей - если можно учитывать нулевой (пустой, размером 0*0) подмассив, то вначале ans=0, иначе - ans="большое по модулю отрицательное число" (число, которое гарантировано меньше самого большого из отрицательных чисел на входе). Просто во втором случае может быть, что весь массив из отрицательных чисел и нету ни одного прямоугольника с сумой 0 или больше. 1