Не могу написать прогу. Условие такое:
Фермер хочет построить на своей земле как можно больший по площади сарай.
Но на его участке есть деревья и хозяйственные постройки, которые он не
хочет никуда переносить. Для простоты представим ферму сеткой размера MxN.
Каждое из деревьев и построек размещается в одном или нескольких узлах сетки.
Прямоугольный сарай не должен ни с чем соприкасаться
(т.е. в соседних с ним узлах сетки не может ничего быть).

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

Задача Должна быть реализована с помощью Динамического программирования.

Здравствуйте, <Аноним>, Вы писали:

А>Не могу написать прогу. Условие такое:
А>Фермер хочет построить на своей земле как можно больший по площади сарай.
А>Но на его участке есть деревья и хозяйственные постройки, которые он не
А>хочет никуда переносить. Для простоты представим ферму сеткой размера MxN.
А>Каждое из деревьев и построек размещается в одном или нескольких узлах сетки.
А>Прямоугольный сарай не должен ни с чем соприкасаться
А>(т.е. в соседних с ним узлах сетки не может ничего быть).

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

А>Задача Должна быть реализована с помощью Динамического программирования.

Идешь сюда, смотришь задачу №11, разбираешься .
Offtopic: а зачем тебе оно надо?

Здравствуйте, HiFix, Вы писали:

HF>Идешь сюда, смотришь задачу №11, разбираешься .
HF>Offtopic: а зачем тебе оно надо?
Судя по формулировке

Задача Должна быть реализована с помощью Динамического программирования.

видимо, для зачета
тут, два раза в год, бывает приток четко сформулированных задач с математическим уклоном

Здравствуйте, FreshMeat, Вы писали:

FM>Здравствуйте, HiFix, Вы писали:

HF>>Идешь сюда, смотришь задачу №11, разбираешься .
HF>>Offtopic: а зачем тебе оно надо?
FM>Судя по формулировке
FM>

FM>Задача Должна быть реализована с помощью Динамического программирования.

Формулировку Динамического программирования в студию! (сам не знаю — хочу узнать).

Здравствуйте, HiFix, Вы писали:

HF>Здравствуйте, FreshMeat, Вы писали:

FM>>Здравствуйте, HiFix, Вы писали:

HF>>>Идешь сюда, смотришь задачу №11, разбираешься .
HF>>>Offtopic: а зачем тебе оно надо?
FM>>Судя по формулировке
FM>>

FM>>Задача Должна быть реализована с помощью Динамического программирования.

HF>Формулировку Динамического программирования в студию! (сам не знаю — хочу узнать).
Система перевода рекурсивных функций из экспоненциальных в линейную зависимость времени выполнения путем сохранения промежуточных результатов функции или их вычисления до основного алгоритма.
Например — числа Фибоначи:

void Calc(int x)
{
    if (x<1) return 0;
    if (x==1) return 1;
    return Calc(x-1)+Calc(x-2);
}

Время выполнения в зависимости от числа растет экспотенциально
При динамическом программировании:

static int tempResult[max];//ессно здесь должен быть динамический массив
void Calc(int x)
{
    if (x<1) return 0;
    if (x==1) return 1;
    if (tempResult[x]!=0)return tempResult[x];
    return (tempResult[x]=Calc[x-1]-Calc[x-2]);
}

Время выполнения линейное, так как используется уже выполненые результаты вычисления функции

В данном случае, классическая задача о ранце с использованием динамического программирования. Решение не привожу, наверняка есть в интере есть до фига информации по данной задаче. После поиска, хотя бы знания останутся.(вот такой я злой)

С уважением, Gleb.

Здравствуйте, GlebZ, Вы писали:
GZ>Решение не привожу, наверняка есть в интере есть до фига информации по данной задаче. После поиска, хотя бы знания останутся.(вот такой я злой)
Искал, читал, задачи решал (ну или пробовал ). Мне просто интересно было по каким критериям оценивается тип задачи (ДП, комбинаторика и т.д.)