Здравствуйте, мне нужен алгоритм, который оптимально позволяет распихать ящики разных размеров внутри контейнера

Здравствуйте, tun, Вы писали:

tun>Здравствуйте, мне нужен алгоритм, который оптимально позволяет распихать ящики разных размеров внутри контейнера

А почему вроде? Разве рюкзак этого не делает?

Здравствуйте, jhfrek, Вы писали:

J>Здравствуйте, tun, Вы писали:

tun>>Здравствуйте, мне нужен алгоритм, который оптимально позволяет распихать ящики разных размеров внутри контейнера

J>А почему вроде? Разве рюкзак этого не делает?

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

Здравствуйте, Нахлобуч, Вы писали:

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

То есть вопрос не в том что упаковать, а в том как упаковать?

Здравствуйте, jhfrek, Вы писали:

J>Здравствуйте, Нахлобуч, Вы писали:

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

J>То есть вопрос не в том что упаковать, а в том как упаковать?

Моя твоя не понимайт...

Проблема рюкзака:
Дана кучка предметов различной массы, и надо выяснить, можно ли положить некоторые из этих предметов в рюкзак так, чтобы масса рюкзака стала равна определенному значению. Более формально, дан набор значений M1, M2, … , Mn и сумма S. Требуется вычислить значения bi, такие что

S = b1M1 + b2M2 + ... + bnMn

Каждое bi может быть либо нулем, либо единицей. Единица показывает, что предмет кладут в рюкзак, а ноль — что не кладут.

Так что получаем, что рюкзак по сути ничего не оптимизирует, а просто говорит, можно ли собрать рюкзак данного веса или нет.

Здравствуйте, Нахлобуч, Вы писали:

J>То есть вопрос не в том что упаковать, а в том как упаковать?

Н>Моя твоя не понимайт...

Однозначно. Рюкзак работает с предметами как с математическими абстракциями, а тебе нужен алгоритм оптимальной укладки физических объектов с учетом их геометрических размеров? Не расчет столько и каких объектов уложить, а как именно уложить?

Здравствуйте, jhfrek, Вы писали:

J>Однозначно. Рюкзак работает с предметами как с математическими абстракциями, а тебе нужен алгоритм оптимальной укладки физических объектов с учетом их геометрических размеров? Не расчет столько и каких объектов уложить, а как именно уложить?

Да мне-то не надо. Я об чем и говорю — рюкзак не оптимизирует и ваабще не предназначен для работы ни с чем иным, кроме как с числами.

Здравствуйте, Нахлобуч, Вы писали:

Н>Да мне-то не надо. Я об чем и говорю — рюкзак не оптимизирует и ваабще не предназначен для работы ни с чем иным, кроме как с числами.

Ну все алгоритмы рано или поздно работают в числами, двоичными, иного компьютерам не дано.

А вот если быть более точным то задача о рюкзаке (задача о загрузке) звучит так:

Пусть надо загрузить рюкзак (самолет, контейнер) грузоподьемностью W n предметами. Пусть число предметов каждого наименования m(i), вес — w(i), прибыль — r(i). Тогда задача — максимизировать Z = r(1)*m(1) + r(2)*m(2) + ...r(n)*m(n), при условии что w(1)*m(1) + w(2)*m(2)+... w(n)*m(n) <= W, и m(1), m(2),... m(n) >= 0 и целые

Так что все таки оптимизирует

Здравствуйте, Нахлобуч, Вы писали:

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

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

Целевая функция — кол-во ящиков каждом ряду. Мы ее пытаемся максимизировать. Пусть у нас есть n ящиков с размерами l, w, h а размер контенера L, W, H. Пусть центр координат лежит в ближнем к нам нижнем левом углу контейнера, а координаты противоположных углов i ящика (xi, yi, zi) и (x'i, y'i, z'i) (заметим что x'-x=l, и т.д)
Заполняем первый ряд ящиками с индексами j1, j2, ...jk
Для них должно быть: Sum((x'j-xj)). для всех j из j1, j2, ...jk <= L, xji>=x'j(i-1), i=1..k
Пусть заполнение не плотное, т.е. для второго ряда y >= Max(yj), для всех j из j1, j2, ...jk
Тогда для второго ряда получаем те же соотнощения плюс yji <= W, i=1..k
Аналогично укладываем остальные ряды. Уложив первый слой укладываем второй, пусть то же неплотно, т.е. считая что z >= Max(Z) первого слоя.
В конце концов мы получим некую упаковку, близкую к оптимальной.

Если нужна плотная упаковка, то прийдется отслеживать Max соответствующих координат в пределах i-го ящика.

ЗЫ. Хотя если число ящиков мало, то можно устроить и полный перебор

Здравствуйте, мне нужна реализация похожей задачи (под переделку) (С++) или советы по реализации.
Дано:
параметры ящиков, их вес (центр тяжести строго по центру) и их количество,
параметры котейнеров и их количество.
Задача:
разместить эти ящики так, что-бы они заняли минимальное количество контейнеров, причём центр тяжести контейнера не должен отклоняться от центра больше чем на 10% ширины по X и на 10% по Y.

Заранее спасибо.

Да, забыл:

всё происходит в 2D

Здравствуйте, tun, Вы писали:

tun>Здравствуйте, мне нужна реализация похожей задачи (под переделку) (С++) или советы по реализации.
tun>Дано:
tun> параметры ящиков, их вес (центр тяжести строго по центру) и их количество,
tun> параметры котейнеров и их количество.
tun>Задача:
tun> разместить эти ящики так, что-бы они заняли минимальное количество контейнеров, причём центр тяжести контейнера не должен отклоняться от центра больше чем на 10% ширины по X и на 10% по Y.

А что тут кроме "жадного" заполнения контейнеров по очереди. Центр тяжести — это всего навсего усложнение условия возможности положить ящик. Берешь самый большой ящик и кладешь его в самый большой контенер, проверяя разумеется условия. Потом следущий по размеру, потом еще и так до исчерпания места...

Здравствуйте, jhfrek, Вы писали:

J>Здравствуйте, tun, Вы писали:

tun>>Здравствуйте, мне нужна реализация похожей задачи (под переделку) (С++) или советы по реализации.
tun>>Дано:
tun>> параметры ящиков, их вес (центр тяжести строго по центру) и их количество,
tun>> параметры котейнеров и их количество.
tun>>Задача:
tun>> разместить эти ящики так, что-бы они заняли минимальное количество контейнеров, причём центр тяжести контейнера не должен отклоняться от центра больше чем на 10% ширины по X и на 10% по Y.

J>А что тут кроме "жадного" заполнения контейнеров по очереди. Центр тяжести — это всего навсего усложнение условия возможности положить ящик. Берешь самый большой ящик и кладешь его в самый большой контенер, проверяя разумеется условия. Потом следущий по размеру, потом еще и так до исчерпания места...

так, если засовывать только самые большие ящики, то останется очень много незаполненого пространства (ящики не квадратные), надо ещё и маленькие воткнуть