Добрый день. 
Дан прямоугольник шириной W и высотой H. Даны N1 окружностей диаметром D1, N2 окружностей диаметром D2...Nk окружностей диаметром Dk. N>=1, k>=1, D>0. Разместить окружности в прямоугольнике так, чтобы
Окружности не пересекались между собой
Окружности не пересекались с границами прямоугольника
Окружности были распределены по всей площади прямоугольника. Т.е. например так, чтобы не было ситуации, когда все окружности "забились" в угол.
Окружности располагались на как можно меньшем количестве горизонтальных/вертикальных осей. Т.е. чтобы была некая сетка осей.
Предложить варианты размещения

Буду рад любой помощи. Задача имеет прикладной смысл на практике - будут производиться электромонтажные коробки с отверстиями для ввода кабелей.

Ну задачка-то тянет на переборную.



И сколько в коробке тех отверстий? на одной стороне, понятно... десяток? два? ну вряд ли сотня... а такое проще руками раскидать. Если, конечно, отверстия не покрывают более половины площади грани - тут вообще уместить бы.

Согласен. Но пока не укладывается в голове каким алгоритмом.

Отверстий может быть порядка 30-40 на одной грани (есть большие коробки). Как правило, конечно, 10-15. Руками можно, но стоит задача написать автоматический расстановщик (далее это будет перекладываться в чертеж автокад). Задача сведена к минимуму - расставить окружности по прямоугольнику. 

Надеюсь, можно задвинуть приблизительно такой постулат - суммарная площадь кругов более чем на порядок превышает площадь прямоугольника? В этих условиях я вполне могу придумать вменяемый и рабочий алгоритм (оптимальности не жди).
А если это соотношение типа 1/2, то даже мыслей никаких нет...

только тут наоборот. Все же окружности - это отверстия, а значит их площадь точно меньше площади прямоугольника. Постулат принимаем. Оптимальности не требуется. Рад принять любую помощь! Спасибо.

Отверстия, так на минуточку, всё-таки круги. Окружности - это их края, границы.
Насчёт наоборота - да, второпях накосячил.

Но в этой фразе главное - именно "на порядок". Не вдвое, не втрое, а минимум раз в десять, а то и больше. 

А с технологией как? 
Окружность это что? Размер входящего кабеля? А соединительные гайки имеют размер? Отверстия должны отделяться друг от друга вполне на определенное расстояние, которое определяется прочностью материала коробки и прикладываемыми к узлу усилиями...

  

Хорошо, условия приняты! я вижу на другом ресурсе тоже в моей теме отписался  надеюсь чего-нибудь совместными усилиями мы все же добьемся!


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

Да. 
http://forum.sources.ru/index.php?showtopic=409076