Алгоритм
Народ, подскажите пожалуйста с алгоритмом.
Суть вот в чем:
1) Есть доски объявлений (размеры разные)
2) Есть объявления, которые размещаются на эти доски (размеры разные)
Нужно при помещении очередного объявления проверить осталось ли место на доске.
К тому же надо нарисовать саму доску и как расположены на ней объявления.
Суть вот в чем:
Работник, вешая очередное объявление, вешает его как-бы на бум, не задумываясь о том, куда повешает следующее. Таким образом при забивании доски получается ситуация, что существует к примеру две незанятые "дыры", к примеру, по 2 см квадратных каждая. Возможно, что эти дыры можно "превратить" в одну, скомпоновав объявления оптимальным способом, и поместить еще одно объявление.
Рисовать это надо, чтобы работник знал как ему надо перевесить объявления.
Ломаю голову уже который день - ничо не могу придумать.
Хотя бы какие-нибудь идеи подкиньте, если кто-нибудь чо-нибудь придумает..
Суть вот в чем:
1) Есть доски объявлений (размеры разные)
2) Есть объявления, которые размещаются на эти доски (размеры разные)
Нужно при помещении очередного объявления проверить осталось ли место на доске.
К тому же надо нарисовать саму доску и как расположены на ней объявления.
Суть вот в чем:
Работник, вешая очередное объявление, вешает его как-бы на бум, не задумываясь о том, куда повешает следующее. Таким образом при забивании доски получается ситуация, что существует к примеру две незанятые "дыры", к примеру, по 2 см квадратных каждая. Возможно, что эти дыры можно "превратить" в одну, скомпоновав объявления оптимальным способом, и поместить еще одно объявление.
Рисовать это надо, чтобы работник знал как ему надо перевесить объявления.
Ломаю голову уже который день - ничо не могу придумать.
Хотя бы какие-нибудь идеи подкиньте, если кто-нибудь чо-нибудь придумает..
Ммм. Сперва вешай самые большие объявления. Начинай с угла (доска-то хоть прямоугоьлная?), далее каждое последующее пытайся втиснуть в свободное место, оставшееся после размещения крупных объявлений (начинай с места рядом с самым большим и по убывающей, объявления обычно крутить нельзя, тут тебе задача упрощается).
Не знаю, насколько оптимален мой вариант, но попробуй.
Не знаю, насколько оптимален мой вариант, но попробуй.
Цитата:
Originally posted by int
Сперва вешай самые большие объявления.
Сперва вешай самые большие объявления.
Не обязательно так. Возможно самое большое объявление по высоте влезет только одно. А вот, допустим объявление поменьше - ровно два. К примеру высота шита 10 см, высота самого большого 7 см, а высота поменьше 5 см. Так лучше размещать сначала объявления поменьше..
Цитата:
Originally posted by int
Начинай с угла (доска-то хоть прямоугоьлная?), далее каждое последующее пытайся втиснуть в свободное место, оставшееся после размещения крупных объявлений (начинай с места рядом с самым большим и по убывающей,..
Начинай с угла (доска-то хоть прямоугоьлная?), далее каждое последующее пытайся втиснуть в свободное место, оставшееся после размещения крупных объявлений (начинай с места рядом с самым большим и по убывающей,..
А куда его "втискивать"? В вертикаль или горизонталь?
Цитата:
Originally posted by int
объявления обычно крутить нельзя, тут тебе задача упрощается).
объявления обычно крутить нельзя, тут тебе задача упрощается).
Задача не упрощается, поскольку объявления крутить можно. Извиняюсь за неточность - под "размерами" я имел ввиду высоту и ширину, а не площадь. Так что можно рассматривать объявления 1х2 и 2х1, как объявления с разными размерами..
Попробуй поискать в направлении задачи о рюкзаке. Насколько я понял, у тебя получается своеобразный "двумерный рюкзак", то есть контрось нужно вести и по длине и поширине.
