Вот задача: Есть N коробок, есть размеры (ширина, высота, длина) есть парамелипипед с размерами (ширина, высота, длина) как узнать сколько поместиться коробок в данный парралелипипед?  Тупо по объему не получиться.... Надо как-то размещать коробки. Встачал алгоритм размещения прямоугольников на плоскости. Что-то пододное надо...
Помогите пожалуйста... Буду всем благодарен...

http://www.packer3d.ru/modules/p3dcontent/?id=omega

задача о рюкзаке

(1) 370 килорублей :)

Да программка не плохая, но хотелось бы узнать алгоритм работы. Или как нибудь связать её с Торговлей 1С...
У них есть какая нибудь библиотека?

http://www.packer3d.ru/modules/p3dcontent/?id=about_ver3
Настройка конфигурации программы "1C Предприятие v7.7" для обмена данными с программой "packer3d v3.xx" модификаций "prof" и "corp".

(2) больше на задачу о раскрое похоже

Задача о рукзаке - самая простоя и высчитывается тупо перебором по объему. Надо что-то вроде этого http://www.packer3d.ru/modules/p3dcontent/?id=omega но только или с интеграцией в 1С или напичанное в 1С или хотсябы алгоритмы, решающие данную проблему.

У нас стоит Торговля на 8.1...

если не ошибаюсь - задача NP-полна, и на 1Ске решаться будет долго, как минимум надо через ВК

Любой алгоритм дискретной оптимизации:
Самый простой, но долгий способ - полный перебор всех вариантов размещения коробок.
Чуть сложнее, быстрее, но не дающий 100% сходимости - генетические алгоритмы.
Ну и далее всевозможные методы отсечений заведомо неоптимальных ветвей дерева вариантов перебора.

Поэтому я и хочу знать алгоритм. Написать программу на С++ и сделать компонент ActivX или библиотеку DLL для расчетов.

Любой алгоритм дискретной оптимизации:
Самый простой, но долгий способ - полный перебор всех вариантов размещения коробок.
Чуть сложнее, быстрее, но не дающий 100% сходимости - генетические алгоритмы.
Ну и далее всевозможные методы отсечений заведомо неоптимальных ветвей дерева вариантов перебора.

Можно ли примеры элгоритмов где-нибудь достать? Или схемы их реализации?

алгоритм дейкстры возьми за основы
пиши на 1С

Алгоритм Дейкстры - если я не ошибаюсь алгоритм нахождения минимального растояния в графах? Каким образом он может помочь?

Думаю плясать надо от жадного алгоритма

Надо решить "3D  задачу о рюкзаке" ))

(16) тогда тем более (15)

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

Про генетические алгоритмы,см:
http://ru.wikipedia.org/wiki/

Если в них разобраться, то реализация может быть даже проще, чем перебор.
(13) Мелкий бес прав, пиши на 1С - видимое преимущество от ВК будет заметно, при соотношении среднего объема коробки к полезному пространству от 1/50.

(18) "http://ru.wikipedia.org/wiki/Генетические_алгоритмы"

Да вот-это мне задачку задал мой начальник. Вечно блин как=что перидумают....

(20) не надо было занятия в вузе пропускать :)

(20) Счастливый человек, тебе хоть интересные задачи дают, а не писать тупые отчеты для пользователей.

До этого давали задачу по отправке машин. У нас более 20 филиалов и постоянно открываються новые. Надо было реализовать оптимальные маршруты доставки груза... Но это задача конечно по сравнению с "3D рюкзаком" - фигня....

Что то сомневаюсь, что грузчики будут укладывать коробки "оптимально" или играть в тетрис.. Скорее всего действительно достаточно будет посчитать количество коробов в слое (предпологая что короб будет ложиться на бОлбшую сторону), а затем исходя из высоты короба посчитать количество слоев.. Только еще не забыдь про допуски, потому как реальные короба это не математические модели, а гнутые кортонные коробки..

Я с этой задачей боролся :) но не доборолся :)

(24) - ярусная укладка при работе алгоритма уже большуя часть "тетрисных" вариантов отсечет.

Да насчет кладовщиков я тоже сомниваюсь. Может сделать так: Вычилять объем необходимой машины или машинн при любой укладки?

Что-то я не понял насчет коробок в слое??? Коробки то разные бывают и по ширене и длине...

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

что-то такое писал - на 3 страницы кода получилось - как раз с ячеистым хранением параллелепипедов в параллелепипедах ;)

(0) слишком много неопределённостей.
какие правила укладки?
(22) а ты пиши не тупые-)

Может все таки проверять тупо по объему. и учитывать погрешность (полную заполняемость) 70 процентов. (Вычитал что грузчики в среднем заполняют машину на 70-75 процентов)? Как сразу мы тут задачу упростили :)))

(32) а ничего, что у машины еще ограничение по весу есть? когда у нас двадцатитонники грузят фуры - там от пола максимум на метр груза....

Кладовщики сейчас укладывают товар в машину на свое усмотрение. При этом товар может находиться как в упаковках так и не в упаковках (это запчасти). Это для упращения можно считать что они все в упаковках.... Вот так...

(33) - не понял? что ты хотел сказать?

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

Сейчас пойду на склад спрашу....

Не у ас наоборот по весу редко бывает. В основном по объему не проходит. :(

(31) Таки пытаюсь не тупые писать, но, если (псевдо)аналитики  требуют, чтобы, в одной табличке была сразу информация из половины регистров, справочников и документов, а что при этом простыня получается, которую впринципе нельзя нормальному человеку охватить взглядом - так, цитирую: "Зато все наглядно!"

(38) тогда правила как кантовать можно, нужно учитывать... в принципе, ИМХО нормально будет, если посчитать 3 варианта - каждой гранью вверх, и так для каждого слоя - а затем выбрать наилучший...

(0) а если исходить из таких условий:
1)Известно где низ коробки
2)все коробки укладываются в одном направлении за исключением последнего ряда сбоку и сзади.
3) Последний ряд укладывается как войдёт.

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

+(41) 4) все коробки одинаковые ;)

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

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

(44) А в чем проблема?
1) Есть заказ филиала, у него есть объем и вес заказа,
2) Есть объем машины и ее грузоподъемность.
3) Сначала проверка, что весь 0.8 объема заказов входит и грузоподъемности автомобиля хватает.
4) Потом порядок укладки заказов филиалов, самый дальний в первую очередь, и так до первой точки - она последняя в укладке.
5) Получаешь объем каждой укладки, потом в этом объеме размещаешь сначала самые большие коробки, на следующем слое поменьше и т.д. При этом проверяешь габариты машины.
6) На оптимальность укладки - можно забить. Все равно объем уложенных заказов будет примерно 80% от объема автомобиля. Иначе их потом выгружать будет трудно.
Успехов )))