Программное распределение маленьких прямоугольников, в больших

[miklenew]

Есть 100 маленьких прямоугольников. Они разные.
И есть 10 больших прямоугольников.
Надо распределить 100 маленьких на 10 больших, чтоб осталось как можно больше больших.
Т.е. эти большие будут потом нарезаны на маленькие. Надо чтоб целых (больших) осталось как можно больше.
Может кто то видел уже какой нибудь готовый велосипед?

[S.Kuskov]

http://habrahabr.ru/post/136225/

[ice]

симплекс-метод

[miklenew]

Цитата:

Сообщение от ice

симплекс-метод

Там какой то вырви мозг.

[miklenew]

В идеале если бы в инете была программа в которую можно было бы подкидывать размеры прямоугольников в текстовом файле. А на выходе другой текстовый файл с координатами распределения.
Задача наверна стара и поэтому могла бы быть каким нибудь дипломным проектом у какого нибудь студента.

[miklenew]

Нашёл список программ
http://c-a-m.narod.ru/computers/soft-raskroj.html

[R.Safianov]

Решал похожую задачу в институте, применял генетические алгоритмы.

[Ace of Database]

В начале 90-х в досовские времена я видел резидентную программу, которая запускала тетрис и играла в него. Программа перехватывала изображение из видеопамяти, анализировала расположение фигур и управляла падающими фигурами, посылая через прерывание коды клавиш в тетрис,
Программист, написавший эту программу, не смог поступить в институт - провалил вступительный экзамен по математике. В результате потом он уехал в Канаду.

[gl00mie]

Про тетрис - это, конечно, очень трогательно, но авторы тех же компьютерных игр решали даже в те времена зачастую куда более затейливые задачи, чем анализ фигур из 4-х квадратиков, рисуемых в видеопамяти сплошной заливкой, и анализ "стакана", куда помещается 10 таких квадратиков в ширину и хрендцать в высоту. И слать нажатия клавиш через прерывания под DOS было излишне: то ли DOS, то ли BIOS (не помню за давностью лет) держала в памяти буфер на 16, кажется, скан-кодов клавиш + указатель на текущую позицию в буфере, до которой успело считать приложение, так что эмулировать нажатия клавиш можно было с помощью записи в обычный байтовый массив. Вот если бы он распознавание capcha написал - это да...

[UNRW]

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

[Ace of Database]

Цитата:

Сообщение от gl00mie

Про тетрис - это, конечно, очень трогательно, но авторы тех же компьютерных игр решали даже в те времена зачастую куда более затейливые задачи, чем анализ фигур из 4-х квадратиков, рисуемых в видеопамяти сплошной заливкой, и анализ "стакана", куда помещается 10 таких квадратиков в ширину и хрендцать в высоту. И слать нажатия клавиш через прерывания под DOS было излишне: то ли DOS, то ли BIOS (не помню за давностью лет) держала в памяти буфер на 16, кажется, скан-кодов клавиш + указатель на текущую позицию в буфере, до которой успело считать приложение, так что эмулировать нажатия клавиш можно было с помощью записи в обычный байтовый массив. Вот если бы он распознавание capcha написал - это да...

Фишка в том, что я вместе работал с тем программистом. Более великих программистов я к сожалению, в реальной жизни не встречал. Даже если брать не программистов, а вообще великих людей, то я всего лишь однажды видел Кобзона на улице, и Макаревича в баре, и еще видел Усатого Няня в комитете по культуре.
Но я встречал много программистов, и каждый из них по-своему хорош. Вообще, я понял, что плохих программистов не бывает. У каждого можно найти что-то интересное.

PS И через прерывание передать нажатие клавиши легче, так как это стандартное API BIOS.