Построить парники, закрывающие огурцы

@Faragor · Регистрация: 28.11.2015

Нужно помочь с задачей.
Задачу сдавать на зачёт, я не знаю как её сделать; она мне кажется очень сложной. Пишу на С++
Задача о огурцах.
/////
Задано поле n x m квадратных ячеек, в каждой из которых могут находиться посадки огурцов.
Необходимо построить парники, закрывающие огурцы. Парники могут быть только прямоугольной формы, только со сторонами,
параллельными сторонам поля. Стоимость строительства одного парника складывается из двух составляющих - известной постоянной
и величины,
пропорциональной площади парника. Парник может накрывать только целое количество ячеек. Выяснить какие варианты
строительства парников наименее затратны при условии,
что закрытыми от непогоды оказываются все ячейки с огурцами.
//////
Мне хотя бы подсказочку с алгоритмом, я вообще вообразить не могу как сделать, хотя бы перебором, так как лучшим вариантом может быть вариант с разными по площади парниками. На вход подаются:
S - цена за клетку 1х1
C - цена за строительство 1 парника
и поле с огурцами в виде нулей и единиц(1 - есть). В общем спасибо заранее.

@nmcf · 28.11.2015, 11:18

Если поле прямоугольное, то одного парника не хватит, что ли?

@Faragor · 28.11.2015, 11:55 **[ТС]**

Пусть поле NxM, тогда если всё замостить парниками цена будет S*N*M+C что не является минимальной(минимальна только в случае когда пользователь укажет S = 0)

@ilja123 · 28.11.2015, 12:05

Допустим поле = 4x3, тогда число ячеек 12.
Наш Коэф. =1000руб. За все поле 12000. Если с огурцами только 3 ячейки, тогда 3000руб.

Мин. цена = мин. ячейке, т.е. 1000руб. Не ????

@Faragor · 28.11.2015, 12:11 **[ТС]**

Нет, у нас ещё учитывается цена за СТРОИТЕЛЬСТВО, так может получиться, что выгодней построить один парник чтобы закрыть 4 клетки при этом закрыв 2 - 3 огурца(цена будет 4S+C), чем строить каждый отдельно, так как цена будет равна 3S+3C. Тут не всё так просто на самом деле.

Добавлено через 49 секунд
Нет, у нас ещё учитывается цена за СТРОИТЕЛЬСТВО, так может получиться, что выгодней построить один парник чтобы закрыть 4 клетки при этом закрыв 2 - 3 огурца(цена будет 4S+C), чем строить каждый отдельно, так как цена будет равна 3S+3C. Тут не всё так просто на самом деле.

@ture · 28.11.2015, 12:33

Мне это нравится. Ей богу. Я пока все думаю.

@ilja123 · 28.11.2015, 12:48

Нам дали поле с расположением ячеек с огурцами. Мы это поле берем, как 2-х мерн. массив. Считаем кол-во занятых ячеек, прибавляем наш коэф. + за строительство:

C++ (Qt)

#include <iostream>
 
using namespace std;
 
int main()
{
    char field[4][3] = {'*', '*', ' ',
                        ' ', ' ', ' ',
                        ' ', '*', ' ',
                        ' ', '*', ' '};//pole 4x3
    int S=0;//ploshad
    int priceK1 = 1000;//koeficient za ploshad
    int priceK2 = 10000;//koef za stroitelstvo
    int sumPrice;//cena itogo
 
    for(int i=0; i<3;i++)
    {
        for(int j=0; j<4; j++)
        {
                if(field[i][j] == '*')
                {
                    S++;
                }
        }
    }
 
    sumPrice = S*priceK1+priceK2;
 
    cout << sumPrice;
 
    return 0;
}

Так не годится ?

Добавлено через 5 минут
Тут не площадь конечно, а ячейки, но в задаче же сказано про кол-во занятых ячеек. Вот мы их и учитываем.

Добавлено через 1 минуту
Поле же можно разбить на квадраты ?

Добавлено через 2 минуты
Я спать

@Faragor · 28.11.2015, 14:07 **[ТС]**

Ну и что ты сделал? Программа явно лажа.
строка 27: Ты построил парников столько сколько огурцов, но почему-то прибавляешь priceK2 один раз.
И тем более ты просто построил на каждый огурец 1 парник - это явно не решение. Так как зависит от цен. Нужно подобрать ОПТИМАЛЬНОЕ по стоимости.

Добавлено через 55 секунд
Напишите о успехах. пожалуйста.

@_Ivana · 28.11.2015, 15:14

Так прошлый раз баклажаны были же вроде... с "праниками"... Какие варианты строительства праников наименее затратны

ЗЫ а вообще, задачка интересная, да.

@ilja123 · 28.11.2015, 15:30

_Ivana, а мне нравится реализация с квадратами. Разбиваешь поле на квадраты. Минимальное кол-во - это площадь всего поля. В примере 4x3 - 12 квадратов. И ввести понятие масштаб. Т.е из 12 при желании можно сделать 48, из 48 можно сделать 96.... Так до тех пор, пока в клетки не уместятся все огурцы\баклажаны.

В изм. площади нужда отпадает, т.к. исп. квадраты, а результат тот же.

@_Ivana · 28.11.2015, 15:35

ilja123, я не понял вашу идею с квадратами, но тут существует очень простой тест - проверить ваше и мое решение на нескольких входных данных и сравнить результаты. У меня по умолчанию "праники" не накладываются друг на друга, но можно поменять пару символов в коде и будет возможность поиска решения как с возможностью наложения, так и без.

@Faragor · 28.11.2015, 16:27 **[ТС]**

Там на Haskell щас буду разбираться, если работает, то я самый счастливый человек в мире!

@_Ivana · 28.11.2015, 16:28

Не по теме:

Если разберешься (не в алгоритме, а в коде), то тоже есть повод порадоваться :)

@Faragor · 29.11.2015, 00:20 **[ТС]**

Преподаватель очень требовательный. Вряд ли.

@ture · 29.11.2015, 10:34

Если потерпишь недельку, то мы успеем пройти на след неделе динамическое программирование.

@Faragor · 29.11.2015, 11:01 **[ТС]**

Ну у меня ещё 3 недели до него.

@Faragor · 30.11.2015, 17:08 **[ТС]**

Не могли бы вы объяснить алгоритм?

@MaD2016 · 17.05.2016, 11:08

Пусть поле NxM, тогда если всё замостить парниками цена будет S*N*M+C что не является минимальной(минимальна только в случае когда пользователь укажет S = 0)

@Faragor 0 / 0 / 0 Регистрация: 28.11.2015 Сообщений: 10
		1
	Построить парники, закрывающие огурцы 28.11.2015, 11:11. Просмотров 1090. Ответов 17 Метки нет (Все метки) Нужно помочь с задачей. Задачу сдавать на зачёт, я не знаю как её сделать; она мне кажется очень сложной. Пишу на С++ Задача о огурцах. ///// Задано поле n x m квадратных ячеек, в каждой из которых могут находиться посадки огурцов. Необходимо построить парники, закрывающие огурцы. Парники могут быть только прямоугольной формы, только со сторонами, параллельными сторонам поля. Стоимость строительства одного парника складывается из двух составляющих - известной постоянной и величины, пропорциональной площади парника. Парник может накрывать только целое количество ячеек. Выяснить какие варианты строительства парников наименее затратны при условии, что закрытыми от непогоды оказываются все ячейки с огурцами. ////// Мне хотя бы подсказочку с алгоритмом, я вообще вообразить не могу как сделать, хотя бы перебором, так как лучшим вариантом может быть вариант с разными по площади парниками. На вход подаются: S - цена за клетку 1х1 C - цена за строительство 1 парника и поле с огурцами в виде нулей и единиц(1 - есть). В общем спасибо заранее. 0

@nmcf 6913 / 5978 / 2709 Регистрация: 14.04.2014 Сообщений: 25,504
	28.11.2015, 11:18	2
	Если поле прямоугольное, то одного парника не хватит, что ли? 0

@Faragor 0 / 0 / 0 Регистрация: 28.11.2015 Сообщений: 10
	28.11.2015, 11:55 [ТС]	3
	Пусть поле NxM, тогда если всё замостить парниками цена будет SNM+C что не является минимальной(минимальна только в случае когда пользователь укажет S = 0) 0

@ilja123 48 / 48 / 6 Регистрация: 24.12.2009 Сообщений: 493
	28.11.2015, 12:05	4
	Допустим поле = 4x3, тогда число ячеек 12. Наш Коэф. =1000руб. За все поле 12000. Если с огурцами только 3 ячейки, тогда 3000руб. Мин. цена = мин. ячейке, т.е. 1000руб. Не ???? 0

@Faragor 0 / 0 / 0 Регистрация: 28.11.2015 Сообщений: 10
	28.11.2015, 12:11 [ТС]	5
	Нет, у нас ещё учитывается цена за СТРОИТЕЛЬСТВО, так может получиться, что выгодней построить один парник чтобы закрыть 4 клетки при этом закрыв 2 - 3 огурца(цена будет 4S+C), чем строить каждый отдельно, так как цена будет равна 3S+3C. Тут не всё так просто на самом деле. Добавлено через 49 секунд Нет, у нас ещё учитывается цена за СТРОИТЕЛЬСТВО, так может получиться, что выгодней построить один парник чтобы закрыть 4 клетки при этом закрыв 2 - 3 огурца(цена будет 4S+C), чем строить каждый отдельно, так как цена будет равна 3S+3C. Тут не всё так просто на самом деле. 0

@ture 538 / 346 / 206 Регистрация: 27.11.2014 Сообщений: 1,043
	28.11.2015, 12:33	6
	Мне это нравится. Ей богу. Я пока все думаю. 0

@Faragor 0 / 0 / 0 Регистрация: 28.11.2015 Сообщений: 10
	28.11.2015, 14:07 [ТС]	8
	Ну и что ты сделал? Программа явно лажа. строка 27: Ты построил парников столько сколько огурцов, но почему-то прибавляешь priceK2 один раз. И тем более ты просто построил на каждый огурец 1 парник - это явно не решение. Так как зависит от цен. Нужно подобрать ОПТИМАЛЬНОЕ по стоимости. Добавлено через 55 секунд Напишите о успехах. пожалуйста. 0

@_Ivana 4454 / 2072 / 263 Регистрация: 01.03.2013 Сообщений: 5,508 Записей в блоге: 22
	28.11.2015, 15:14	9
	Сообщение было отмечено Faragor как решение Решение Так прошлый раз баклажаны были же вроде... с "праниками"... Какие варианты строительства праников наименее затратны ЗЫ а вообще, задачка интересная, да. 1

@ilja123 48 / 48 / 6 Регистрация: 24.12.2009 Сообщений: 493
	28.11.2015, 15:30	10
	_Ivana, а мне нравится реализация с квадратами. Разбиваешь поле на квадраты. Минимальное кол-во - это площадь всего поля. В примере 4x3 - 12 квадратов. И ввести понятие масштаб. Т.е из 12 при желании можно сделать 48, из 48 можно сделать 96.... Так до тех пор, пока в клетки не уместятся все огурцы\баклажаны. В изм. площади нужда отпадает, т.к. исп. квадраты, а результат тот же. 0

@_Ivana 4454 / 2072 / 263 Регистрация: 01.03.2013 Сообщений: 5,508 Записей в блоге: 22
	28.11.2015, 15:35	11
	ilja123, я не понял вашу идею с квадратами, но тут существует очень простой тест - проверить ваше и мое решение на нескольких входных данных и сравнить результаты. У меня по умолчанию "праники" не накладываются друг на друга, но можно поменять пару символов в коде и будет возможность поиска решения как с возможностью наложения, так и без. 0

Опции темы

@Faragor 0 / 0 / 0 Регистрация: 28.11.2015 Сообщений: 10
	28.11.2015, 16:27 [ТС]	12
	Там на Haskell щас буду разбираться, если работает, то я самый счастливый человек в мире! 0

@_Ivana
	28.11.2015, 16:28 #13
	Не по теме: Если разберешься (не в алгоритме, а в коде), то тоже есть повод порадоваться :) 0

@Faragor 0 / 0 / 0 Регистрация: 28.11.2015 Сообщений: 10
	29.11.2015, 00:20 [ТС]	14
	Преподаватель очень требовательный. Вряд ли. 0

@ture 538 / 346 / 206 Регистрация: 27.11.2014 Сообщений: 1,043
	29.11.2015, 10:34	15
	Если потерпишь недельку, то мы успеем пройти на след неделе динамическое программирование. 0

@Faragor 0 / 0 / 0 Регистрация: 28.11.2015 Сообщений: 10
	29.11.2015, 11:01 [ТС]	16
	Ну у меня ещё 3 недели до него. 0

@Faragor 0 / 0 / 0 Регистрация: 28.11.2015 Сообщений: 10
	30.11.2015, 17:08 [ТС]	17
	Не могли бы вы объяснить алгоритм? 0

@MaD2016 0 / 0 / 0 Регистрация: 17.05.2016 Сообщений: 4
	17.05.2016, 11:08	18
	Пусть поле NxM, тогда если всё замостить парниками цена будет SNM+C что не является минимальной(минимальна только в случае когда пользователь укажет S = 0) 0

Построить парники, закрывающие огурцы

Решение