задачка на сообразительность

09.03.2007, 14:41

нужно придумать алгоритм (не обязательно оптимальный) для следующей задачи:

Задача о максимальном объёме

Имеются m кубов с длинами рёбер a1, a2, . . . , am и параллелепипед размера h × w × d. Найти некоторое подмножество кубов, которые нужно разместить внутри параллелепипеда таким образом, чтобы они не пересекались и заполняли максимальную часть объёма параллелепипеда.

Insya · 09.03.2007, 15:35

ну если особо не думать, то можно сделать так: выбрать минимум из h, d, w, найти 4 набора кубов, сумма ребер которых(из каждого) максимально приближенa к min(h,d,w), затем выбрать второе по величине значение из h,d,w, проделать то же самое с оставшимися кубами, ну и то же самое сделать для последнего оставшегося значения из hdw. Не забывать учитывать, что когда для высоты, например, выбраны 4 набора кубов, то для ширины и глубины в наборе кубов будет уже два крайних. Вот, потом таким же образом заполнить стенки параллепипеда, затем "тело". Вряд ли ты что-то понял из моих слов, т к объяснить это без картинки и сидящего рядом человека очень трудно

)

pod · 09.03.2007, 18:21

Замуж, дура, срочно замуж!!! (с)

kainen · 09.03.2007, 20:14

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

09.03.2007, 14:41	#1
Громозека Гость Нарушения:[Посмотреть]	задачка на сообразительность нужно придумать алгоритм (не обязательно оптимальный) для следующей задачи: Задача о максимальном объёме Имеются m кубов с длинами рёбер a1, a2, . . . , am и параллелепипед размера h × w × d. Найти некоторое подмножество кубов, которые нужно разместить внутри параллелепипеда таким образом, чтобы они не пересекались и заполняли максимальную часть объёма параллелепипеда.

09.03.2007, 15:35	#2
Insya online(); Регистрация: 24.01.2006 Адрес: Гатчина Нарушения:[Посмотреть]	ну если особо не думать, то можно сделать так: выбрать минимум из h, d, w, найти 4 набора кубов, сумма ребер которых(из каждого) максимально приближенa к min(h,d,w), затем выбрать второе по величине значение из h,d,w, проделать то же самое с оставшимися кубами, ну и то же самое сделать для последнего оставшегося значения из hdw. Не забывать учитывать, что когда для высоты, например, выбраны 4 набора кубов, то для ширины и глубины в наборе кубов будет уже два крайних. Вот, потом таким же образом заполнить стенки параллепипеда, затем "тело". Вряд ли ты что-то понял из моих слов, т к объяснить это без картинки и сидящего рядом человека очень трудно ) Последний раз редактировалось Insya. 09.03.2007 в 16:16.

09.03.2007, 18:21	#3
pod But the cat came back... Регистрация: 24.01.2006 Адрес: Gtn&Spb Нарушения:[Посмотреть]	Замуж, дура, срочно замуж!!! (с) __________________ В этом вашем интернете хрен поймешь, кто прикалывается, а кто реально дебил. (с)

09.03.2007, 20:14	#4
kainen lsd made me a prostitute Регистрация: 24.01.2006 Нарушения:[Посмотреть]	Не надо ничего выдумывать и придумывать, учите линейное программирование.