У меня есть потребность усложненного решения задачи о рюкзаке.
Помимо стандартного условия сложной задачи:

Если кто-то не сталкивался, условие следующее: есть набор предметов разной стоимости и веса
Найти набор сумма которого по весу будет не более вместимости рюкзака, а ценность содержимого максимальная описание есть на wiki -Knapsack_problem
-мое ограничение алгоритма, не все элементы рюкзака имеют ценность самостоятельно.

Если на примере. Есть 2 элемента - пистолет, доп.магазин для него и глушитель. Сам по себе глушитель ценности не имеет, также как и магазин. Если в рюкзаке нет пистолета, то его(этот предмет) не стоит брать в принципе.

В моем случае максимум 800 элементов.
Попытался прямым перебором. С подстановками комбинаций.
Т.е. решал типичную сложную задачу про рюкзак для случаев:
Пистолет
Пистолет+глушитель
Пистолет+доп.магазин
Пистолет+глушитель+доп.магазин

реализация расчета выполняется нереально долго. (мои ограничения по времени превышает в 5 раз и более)

Попробовал жадный алгоритм, работает очень быстро, но есть пара багов на которые нет решения
Метод работает так:
- Создаем эффективность единицы массы (т.е. цена за кг) т.к. в имеющемся у меня условии у самого нужного из направления предмета самая высокая (т.е. если пистолет нужнее всего то он будет самым эффективным на грамм, если следующий по эффективности глушитель та же история )
- сортируем по убыванию, так получаются, что главные предметы в начале списка (пистолеты)
- отбираем до набора веса
- если последний элемент нельзя взять, берет следующий после него по эффективности.
- если эффективнее выложить несколько предметов чтобы взять этот, то так и делает

в данном алгоритме дыра, собственно, которую не могу решить

допустим есть предметы массы, отсортированные по убыванию эффективности 1 кг массы
6 - 100 руб на кг
5 - 91 руб на кг
6 - 90 руб на кг
надо взять 12 кг.

Алгоритм берет 6 и 5 кг. Хотя эффективнее с точки зрения общей стоимости взять две вещи весом 6 кг. Как "надоумить" его чтобы он взял 6 и 6. При этом чтобы алгоритм был "жадным" для нужного быстродействия.

p.s. сортировать по суммарной эффективности не получится. Пистолеты сразу выкинут все глушители и магазины, а это не лучшее решение.
На самом деле задача из ритейла и немного сложнее, я для удобства привел пример в пистолетах. Если кого заинтересует, расскажу что на самом деле делается. Реализовано в VBA, извините, что многа букаф, уже просто не первый день пытаюсь решить и гуглить.

.Михаил.,Спасибо за участие.
Мой первый метод и есть аналог метода Лагранжа определенным образом спроецированный на мою задачу. Суть в том, что ограничения, которые имеются у меня и делают задачу нелинейной и методом прямого перебора пытаюсь решить множество линейных задач.
Но только как я и писал не помогает - долго для 800 элементов расчет производится.

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

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

Пистолет - 1.. Пистолет - 100
Компонент к пистолету N - 1 ... Компонент к пистолету N - 7
где N = 1..100

итого максимум 800 элементов

Я пытаюсь решить задачу для следующих случаев
1. В наборе только - Пистолет - 1.. Пистолет - 100
2. В наборе Комбо1( Пистолет - 1 & Компонент к пистолету 1 - 1)+ Пистолет 2.. Пистолет 100
3. В наборе Комбо1( Пистолет - 1 & Компонент к пистолету 1 - 1 & Компонент к пистолету 1 - 2)+ Пистолет 2.. Пистолет 100
...
i) Комбо 1 - (Пистолет1 & все компоненты к пистолету 1) +...+ Комбо 100 (Пистолет100 & все компоненты к пистолету 100)

проблема в том, что i это очень большое число.
На один расчет я трачу 0,495 секунды на рабочем двухядернике. Даже для 800 случаев( а случаев гораздо больше, непомню формулу комбинаторики которая производит этот расчет количества комбинаций) расчет продолжается 6 минут. Мой предел 1 минута.

Dmitry 123Каа-то попадалась аксиома что не существует решения задачи о раскрое.
Более того, если найдется решение для любой из подобных задач, то найдется и решение для всего класса задач. Но это было лет двадцать назад когда мы пытались сделать задачку по загрузке плавбазы морепродуктами, баластом, водой и прочим стафом.

Сейчас есть сайт где такой расчет можно онлайн бесплатно сделать или купить примочку к 1С или самостоятельную :) Создает даже погрузочный лист (порядок загрузки). Кстати делает весьма недурно, судя по "понтам" на сайте. И по 3D примерам расчетов. На фуру 20 тонную от 30 до 300 секунд тратит.
Я натыкался пока искал решение. Если еще интересует могу вечером ссылку дать, на рабочем компе нет.

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

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

.Михаил., займет время
сча попробую

.Михаил.
Поймите, мне нужен имеено сам код, а не то как Вы его реализовывали. Проблема медленной работе может быть в самом коде, в том как Вы его реализуете, какие используете логические конструкции, какие используете функции и методы... каждое действие затричивает процессорное время. Приведу пример. Необходимо х умножить на 5. Сделать можно двумя способами: х*5 или х+х+х+х+х . Второй способ намного быстрее, потому что на сложение процессор меньше тратит времени, чем на умножение.

Понятно. Просто самой этой конструкции у меня уже нет. Я отказался от нее т.к. быстродействие было не утешительным. Реализовал все жадным алгоритмом.
А так вся концепция на циклах ForTo и работа с массивами. В общем поищу. В какой то итерации кода у меня еще оставалась эта схема.

Концептуальных идей кроме оптимизации кода нет? Просто я на 99% думаю, что само количество вычислений настолько огромно, хотябы 100! если у меня 100 вариантов это уже очень много.

.Михаил., ок. Чуть попозже поищу и выложу.
У кого нибудь ещё, будут идеи?

Valerпопробуйте такой вариант
1 этап
находите все варианты загрузки от максимальной ( 100 % )
до например 90%
без учета стоимости компонент
учитывая только вес

2 этап
по всем вариантам 1 этапа считаете стоимость
с учетом взаимовлияния компонент на стоимость

это мысль, надо так попробовать будет
только ещё раскурить, но концепция ясна.
спасибо