Жадина с рюкзаком, или немножко о поиске лучшей жизни

23.12.15

Разработка - Математика и алгоритмы

Полагаю, все программисты когда-то слышали о "жадном" алгоритме. Возможно кто-то из них слышал и об алгоритме "Рюкзак". В данной статье я попытаюсь максимально простым языком описать, как это работает.

Если вы не можете объяснить что-то ребенку двенадцати лет, то, скорее всего, вы это и сами не знаете...

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

 

"Жадный" алгоритм: бери больше - кидай дальше!

Собственно, суть жадного алгоритма сводится к тому, что мы берем список чего либо и упорядочиваем его от большего к меньшему. Дальше в цикле берем элемент, смотрим, влезает ли он в оставшееся место. Если влезает - забираем элемент в список нужных и уменьшаем свободное место. И так до последнего - самого маленького - элемента. Это как в притче о полном стакане: сначала камни, потом песочек, потом водичка, потом еще соль в водичке расстворить можно...

В принципе, код тут весьма простой и особых пояснений, полагаю, не требует, пишу его на псевдоязыке 1С с придуманными функциями и методами:

  // определмим массив для элементов
  Данные = Новый Массив();
  // заполним массив случайными числами
  Для А = 1 По 100 Цикл
    Данные.Добавить(СлучайноеЧисло(100));
  КонецЦикла;
  // упорядочим массив
  Данные.СортироватьВОбратнуюСторону(); // да, такого метода у массива нет, но нам так надо
  // реализуйте это сотней других способов!
  // определим нашу переменную потребность )))
  СколькоНамНужно = 2500;
  // определим массив результатов, в которй будем складывать подходящие вещички
  Результаты = Новый Массив;
  // пройдемся по массиву
  Для Каждого Данное ИЗ Данные Цикл
    Если Данное <= СколькоНамНужно Тогда
      Результаты.Добавить(Данное);
      СколькоНамНужно = СколькоНамНужно - Данное;
    КонецЕсли;
  КонецЦикла;
  // предположим, что 1С умеет распечатывать переменные по образу и подобию правильных интерпретаторов
  var_dump(Результаты);

Собственно, что мы сделали?

1. Заполнили массив случайными числами от 1 до 100 (или от 0).

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

3. Определились с потребностями (2500 - это половина половины максимума: предположу, что 50% случайных чисел были больше 50, 50% - меньше 50, в среднем сумма 100 чисел должна быть в районе 5 000, 2 500 - половина, чтобы часть элементов оказалась лишней на этом празднике жизни).

4. Пробежались по массиву и отложили подходящие элементы в другой массив.

5. Попали в сказку и напечатали массив результатов одной командой.

Сразу стоит отметить, что полученный нами результат может быть неидеальным, ибо чтобы получить идеальный результат жадного алгоритма слишком мало, а полный перебор всех вариантов займет очень много времени (100! итераций, а "!" здесь - это обозначение факториала, который, как всем известно, равен произведению последовательности целых чисел с единицы до, в данном случае, ста: 1 * 2 * 3 * 4...* 99 * 100 - а это очень много!).

Вывод номер раз

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

Продолжаем разговор: "Третий результат? Давай его улучшим!"

Итак, у жадного алгоритма высокая скорость, но низкая эффективность. Можно ли его улучшить? Да. Для этого нам нужно будет пробежаться по массиву результатов и применить жадный алгоритм для каждого его элемента с учетом оставшихся в исходных данных значениях. При этом искомая сумма будет равна ИскомаяСумма - СуммаРезультата + ТекущееЗначениеРезультата.

Другими словами, нам надо найти решение лучше, чем уже найденное. Для этого при сбрасывании данных в результирующий массив мы должны убрать его из исходных данных. Дальше для каждого значения результата мы будем запускать цикл жадного алгоритма по оставшимся значениям исходных данных. При этом текущей искомой суммой будет разница между общей искомой суммой и суммой элементов результата. Т.е. если мы при первом обходе нашли вместо 2500 всего лишь 2450, то нам нужно найти в оставшихся элементах 50 + значение текущего элемента результата. Если в итоге получилось лучше, чем было (т.е. сумма найденных из оставшихся элементов исходных данных оказалась больше, чем сумма текущего элемента результата), то мы текущий элемент результата переносим в исходные данные, а найденными элементами, улучшившими результат, этот результат дополняем и из исходных данных их убираем.

Надеюсь, не слишком сумбурно описал. Кто не понял - пишите в комментариях, постараюсь дообъяснить по мере сил.

Вывод номер два:

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

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

Рюкзак, или давайте ограбим музей

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

1. Их можно было унести - ограничение по массе.

2. Они должны стоить как можно дороже.

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

Итак, структура таблицы должна быть такая: колонки - это масса, строки - это лучшие варианты для масс по конкретному предмету.

Прадположим, что у нас есть пять предметов с массой/стоимостью: 10/1000; 15/700; 20/1500; 25/1450; 40/1800. Также ограничим грузоподъемность грабителя пятьюдесятью килограммами. В итоге получим такую табличку:

 Масса/Стоимость    0 кг   10 кг 15 кг  20 кг 25 кг 30 кг 35 кг 40 кг 45 кг 50 кг  комментарий 
 10 / 1000   0  1000   1000   1000   1000   1000   1000   1000   1000   1000   для первой вещи лучший результат от 10 кг равен 1000 у.е., до 10 кг равен нулю 
 15 / 700   0  1000    1000  1000  1700  1700  1700  1700  1700  1700  для второй вещи - от 10 и до 25 - 1000 у.е., от 25 до 50 - 1800 
 20 / 1500   0  1000  1000  1500  1700  2500  2500  2500  3200  3200  для третьей вещи - от 10 до 20 - 1000, до 25 - 1500, до 30 - 1800, до 45 - 2500, дальше - 3200
 25 / 1450   0   1000  1000   1500   1700   2500  2500   2500  3200  3250   -- // --
 40 / 1800   0   1000  1000  1500  1700  2500  2500  2500  3200  3250  -- // --   

 

Как, собственно, мы построили эту таблицу? Все достаточно просто: в цикле для каждой вещи мы заполняли стоимость. В колонках у нас масса (я взял кратно 5 кг, т.к. у нас массы всех предметов кратны 5 кг, но разницы нет и для кратности в 1 грамм, просто у нас таблица сильно вырастет вширь), в строках лучший результат на текущий момент. Для каждой вещи лучший результат имеет смысл смотреть тогда, когда мы дошли до колонки с ее массой. До этой колонки мы просто копируем данные из предыдущей строки. Для первой вещи начальные колонки мы заполняем нулями. Когда мы доходим до ячеек с массой, большей или равной массе текущей вещи, мы должны сравнить, что лучше: стоимость этой вещи + лучшая стоимость для предыдущей строки с массой, меньшей текущей на массу текущей вещи, или стоимость текущей массы из предыдущей строки...

Давайте разберем один табличный пример, чтобы стало и ежу понятно. Вот у нас есть третья строка с массой 20 кг и стоимостью 1500 у.е. Мы копируем значения предыдущих результатов до ячейки "15" (или "19", если у вас кратность в 1 кг). В итоге копируем из второй строки в третью следующие числа: 0, 1000, 1000 (колонки "0", "10" и "15"). Т.е. для масс, меньших чем 20 кг, лучшая полученная стоимость для 0 кг - 0 у.е., для 10 кг - 1000 у.е., для 15 кг - 1000 у.е. Дальше, начиная с 20-й колонки, нам нужно сравнить, что лучше: предыдущий результат для массы (20-20 = 0 кг - колонка "0") + стоимость текущей вещи или предыдущий результат для 20 кг. Предыдущий результат (из строки "15 / 800" колонки "20") равен 1000 у.е., а новый результат  = 0 у.е. + 1500 у.е. = 1500 у.е. Новый результат больше - помещаем его в колонку "20" строки "20 / 1500". Дальше проверяем то же самое для 25 кг: старый лучший результат = 1800 у.е., новый = 25 кг - 20 кг (вес текущей вещи) = 5 кг / 0 у.е. + 1500 у.е. = 1500 у.е. Этот результат оказывается меньше - берем старый рекорд. Для 30 кг уже 10 кг (1000 у.е.) + 20 кг (1500 у.е.) = 2500 у.е. и это лучше, чем 1800 у.е. предыдущего результата.

Итак, математическая модель:

1. Определим двумерный массив А(м, н), где м - предельная масса (в минимальных единицах, которые вам нужны: граммы, килограммы, центнеры, тонны, ...), н - количество вещей. Индексы массива начинаются с 0.

2. Заполним для первой вещи значения массива А(Для м = 0 По "масса вещи" - 1, 0) = 0. Заполним остальные ячейки стоимостью первой вещи.

3. Выберем следующую вещь.

4. Заполним все столбцы с индексом массы меньше массы данной вещи из предыдущей строки.

5. Для остальных столбцов проверяем, что больше: стоимость вещи + стоимость из предыдущей строки для столбца (текущий столбец - масса текущей вещи) или стоимость для текущего столбца из предыдущей строки. То, что больше, помещается в текущий элемент массива.

6. Есть еще вещи? Да - 3, иначе выход.

Надеюсь, что все понятно. Напишем код на 1С:

  МассивВещей = Новый Массив();
  КоличествоВещей = 100;
  Для Х = 1 по КоличествоВещей Цикл
    МассивВещей.Добавить(Новый Структура("Масса, Цена", СлучайноеЧисло(50), СлучайноеЧисло(1000) * 1000));
  КонецЦикла;
  // создадим двумерный массив (в принципе, это массив массивов, но мне лень это писать - поэтому сделал так )
  А = Новый Массив(50, КоличествоВещей); // - = это псевдокод = -
  Для Х = 0 по МассивВещей[0].Масса-1 Цикл
    А[Х,0] = 0;
  КонецЦикла;
  Для Х = МассивВещей[0].Масса по 50 Цикл
    А[Х,0] = МассивВещей[0].Стоимость;
  КонецЦикла;
  Для У = 1 ПО МассивВещей.ВГраница() Цикл // цикл по оставшимся вещам
    Для Х = 0 по МассивВещей[У].Масса-1 Цикл
      А[Х,У] = А[Х,У - 1]; // переносим предыдущие лучшие результаты для меньших масс
    КонецЦикла;
    Для Х = МассивВещей[У].Масса по 50 Цикл
      А[Х,У] = Макс(А[Х,У - 1], А[Х - МассивВещей[У].Масса,У - 1] + МассивВещей[У].Стоимость); // помещаем тот результат, который оказался лучше
    КонецЦикла;
   КонецЦикла; // вещи

Итак, мы получили заполненную таблицу. Остается достать из нее данные. В самой последней ячейке (А[50, КоличествоВещей-1]) будет лучший результат. В нашей таблице выше - это 3250 у.е. Теперь нам надо по этой таблице пробежаться вверх и проверить, меняется ли результат. Для последней вещи результат не меняется, поэтому ее брать не надо. Для предпоследней - меняется. Берем: 25 кг / 1450 у.е. Дальше уже смотрим изменения для массы, которая меньше на массу взятой вещи (50 - 25 кг = 25 кг осталось). Дальше у нас в колонке 25 кг результат меняется для вещи 15 кг / 800 у.е. Осталась масса 10 кг. Ее берем из самой первой строки, если там не ноль: 10 кг, 1000 у.е. В итоге у нас массы: 25 + 15 + 10 = 50 кг, сумма = 1450 + 1500 + 800 = 3250 у.е. Оптимально!

Давайте напишем код получения вещей по таблице:

ОставшаясяМасса = 50;
МассивЛучшихВещей = Новый Массив;
Для Х = МассивЛучшихВещей.ВГраница По 1 Цикл // обратный цикл, не помню, умеет ли так 1С, но не вижу проблем реализовать и иначе, если что ))
  Если А[ОставшаясяМасса, Х] <> А[ОставшаясяМасса, Х - 1] Тогда
    МассивЛучшихВещей.Добавить(МассивВещей[Х]);
    ОставшаясяМасса = ОставшаясяМасса - МассивВещей[Х].Масса;
  КонецЕсли;
КонецЦикла;
Если А[ОставшаясяМасса, 0] <> 0 Тогда
    МассивЛучшихВещей.Добавить(МассивВещей[0]);
КонецЕсли;

В заключение...

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

рюкзак жадный алгоритм программирование оптимизация

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1714    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4316    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7343    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7817    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4414    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8793    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7713    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. BigB 191 23.12.15 21:27 Сейчас в теме
(0) забористая у вас трава
savostin.alex; Manoshkin; acanta; d.menyailov@ngslab.ru; Рязанский; fomstas; Shmell; bulpi; WhiteOwl; +9 Ответить
2. karpik666 3759 24.12.15 07:41 Сейчас в теме
Ошибка в таблице вместо 3200 должно быть 3300, и так дальше немного неверно.
starik-2005; +1 Ответить
6. starik-2005 3031 24.12.15 10:13 Сейчас в теме
(2) karpik666, ну я ждал, когда кто-нибудь заметит ))) Рад, что хоть кто-то дочитал до конца! Но это ошибка в расчетах, а не в алгоритме.
8. starik-2005 3031 24.12.15 11:55 Сейчас в теме
(2) karpik666, исправил цифры. Теперь все ок?
9. karpik666 3759 24.12.15 12:24 Сейчас в теме
(8) почти, в комментариях теперь цифры расходятся с таблицей
Плюс в тексте теперь вы изменили 800 на 700, а в тексте нет
сумма = 1450 + 1500 + 800
10. starik-2005 3031 24.12.15 12:46 Сейчас в теме
(9) karpik666, чьйорд побьери, михаил светлоф ту-ту ))) Я тут статью отредактировал и нажал случайно "сохранить в черновик". В итоге с меня сняли 20 стартманей - пришлось писать в техподдержку, поэтому ну его нафиг редактировать эти статьи ))) Главное чтобы понятно было даже детям. А калькулятор я не догадался использовать - ведь основа статьи в описании принципа и коде, а не в правильной математике, подсчитанной в уме...
11. minimajack 80 24.12.15 12:48 Сейчас в теме
(10) да хрен ногу сломит...
в итоге оптимально должно быть 3200
10 /1000
20/1500
15/700
12. starik-2005 3031 24.12.15 12:55 Сейчас в теме
(11) minimajack, да, Вы правы. Просто я промахнулся с расчетами и вычислил в уме не совсем правильно, поэтому пришлось потом редактировать статью, но отредактировал я ее не до конца, ибо с удивлением обнаружил, что с меня за отмену публикации сняли 20 стартманей и поспешил вернуть все назад, не завершив редактирование до конца.

По поводу лучшего результата, то он получается именно за счет построения таблицы и потом нахождения в таблице строк, улучшивших результат. Попробуйте сами таблицу построить в соответствии с описанием алгоритма (в той же Calc или Excel).
13. minimajack 80 24.12.15 12:57 Сейчас в теме
(12) свой результат я получил "имитацией отжига"...и долго удивлялся почему цифры не сходятся
14. starik-2005 3031 24.12.15 13:01 Сейчас в теме
(13) minimajack, имитация отжига и генетический алгоритм могут не дать точного результата, ибо они оптимизируют выборку. Если в них использовать бесконечную оптимизацию, то они могут обойти все варианты за Х! раз, ибо нет предела совершенству. В этом они похожи на жадный алгоритм, но, конечно, приводят к лучшему результату чаще.

Пример тому - периодическое тупление оптимизатора запросов, который работает на базе генетического алгоритма.
15. Шёпот теней 1779 24.12.15 13:15 Сейчас в теме
(14) просто интересно как "генетический алгоритм" может оптимизировать выборку ???

создали популяцию одного набора деталей куртки ... в итоге получили детали штанов ???

... вотВОПРОСвот ...

я не силён в "численных методах" к коим относится "Алгори́тм имита́ции о́тжига" из группы "Ме́тоды Мо́нте-Ка́рло" но как его ТЫ будешь применять ??? для оптимизации выборки ???

.. совсемУЖЖЖсовсем ...
16. starik-2005 3031 24.12.15 13:20 Сейчас в теме
(15) Шёпот теней, ну принципы этих алгоритмов в том, что создается "случайная" популяция - обычный рандом. Потом происходят случайные перестановки, приводящие к улучшению или ухудшению результата. Дальше все это повторяется до бесконечности. В 18 веке был придуман такой метод расчета числа pi с помощью "бросания иголки на пол" - это примерно та же тема.
17. minimajack 80 24.12.15 13:20 Сейчас в теме
(15) Шёпот теней, там используется фитнес функция которая выбирает лучших...скорее всего это и есть оптимизация
3. karpik666 3759 24.12.15 07:57 Сейчас в теме
В заключении вы упомянули, что данную задачу можно применять для определения раскроя, как данный метод можно адаптировать к нему, к примеру задача: дано: макет самый простой - прямоугольный, но ширина и длина у каждого разная, есть ткань определенной ширины и длины, нужно максимально плотно раскроить ткань, чтобы оставалось как можно меньше обрезков, если учитывать площадь макета как ценность в данной задаче, то она не учитывает форму макета, так как по расчету можно поместить на ткань 4 макета, а фактически 3, но с кучей обрезков, так как по форме он не влезает.
4. Шёпот теней 1779 24.12.15 09:11 Сейчас в теме
(3) karpik666,

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

задача, например, раскроя ткани (резка из листа , плит и пр.) уже двумерная (принципы те же)
1. сначала описываем геометрию деталей
2. решаем раскладку методами оптимизации ((линейные, целочисленные и эвристические)
2.1. Симплекс-метод - линейное убывание при локальной оптимальности (Л. В. Канторович "Математические методы организации и планирования производства" (1939 г.))
2.2.симплекс-методом» — метод оптимизации произвольной функции. (Метод Нелдера — Мида)

и много других

Общее решение: http://www.rusnauka.com/34_VPEK_2012/Matemathics/4_121653.doc.htm
FarhadIlyazov; bulpi; karpik666; +3 Ответить
5. Программулькин 301 24.12.15 09:31 Сейчас в теме
"пишу его на псевдоязыке 1С" - аФтора на кол!!
user1041486; +1 1 Ответить
7. starik-2005 3031 24.12.15 10:14 Сейчас в теме
(5) Программулькин, "псевдоязык" - это не то, что Вы подумали. Это некоторые функции, которых в языке нет. Т.е. с "мнимыми/ложными функциями".
Артано; Дмитрий74Чел; +2 Ответить
18. DoctorRoza 24.12.15 13:52 Сейчас в теме
+. чтобы окупить вложения
19. starik-2005 3031 24.12.15 13:54 Сейчас в теме
(18) DoctorRoza, да я особо не старался - ошибся вон в цифрах )))) Цель была в том, чтобы максимально просто все объяснить.
26. PrinzOfMunchen 83 25.12.15 06:00 Сейчас в теме
(19) благодарю, хоть кто-то объяснил так, что наконец-то до конца всё дошло..)))
27. starik-2005 3031 25.12.15 10:35 Сейчас в теме
(26) PrinzOfMunchen, очень рад, что получилось объяснить на столько хорошо)))
20. artspeed 179 24.12.15 16:24 Сейчас в теме
Прочитав статью осознал свою никчемность.
Бывают же умные люди......
Простите за оффтоп.
21. starik-2005 3031 24.12.15 17:13 Сейчас в теме
(20) artspeed, да ну дадно Вам! Я сам с этимне за три минуты разобрался - просто интересно было.
22. karpik666 3759 24.12.15 17:17 Сейчас в теме
(20) artspeed, почитай статьи ildarovich вот его понимают вообще единицы. Кстати у него тоже была статья про алгоритм 3d упаковки, очень занимательная статья.
23. starik-2005 3031 24.12.15 18:04 Сейчас в теме
(22) karpik666, действительно у него много классных статей. Он, кстати, по большому счету использовал жажный алгоритм в языке запросо. Он вообще любит теорию и в принципе не сколько рабочие алгоритмы, сколько экстремальные красивые ситуации. Рекомендую!
28. CheBurator 3119 25.12.15 13:39 Сейчас в теме
(22) я общался с Ильдаровичем. От его выкладок вообще офигеваю (сам вообще ни в зуб ногой). а 3d упаковка его пробовал у себя запустить, переписывался с ним в т.ч. - лажает. плохо упаковывает. пока что для упаковки лучше 3D-Packer - не видел, с его использованием у меня складской оператор вместимость ячеек считает по товарам.
29. starik-2005 3031 25.12.15 13:43 Сейчас в теме
(28) CheBurator, ну а что Вы хотите от жадного алгоритма, реализованного больше как "интересная фича" в языке запросов? Не будет он грамотно упаковывать никогда )))
30. starik-2005 3031 25.12.15 13:48 Сейчас в теме
(28) CheBurator, кстати, навеяло Вашим сообщением. Как-то в 80-х японцы поставили перед собой две задачи: создать тачку, не хуже, чем мерс - получился лексус. А вторая задача - создать процессор пятого поколения - с этим они обосрались (извините, но так и есть) по полной программе. Пока они пять лет мутили этот проц, продукция 4-го поколения от интела ушла так далеко вперед, что японцы должны были дружной командой сделать себе "ХарюКири" )))

Как бы мысль в том, что миллиард операций в секунду делает сейчас ваш проц, а если на нем несколько ядер - и больше. Так вот периодически для не сильно большой выборки можно размещать что-то в чем-то даже методом полного перебора вариантов, находя лучший результат. Все упирается в скорость кода - 1С тут, конечно, совершенно не вариант. Я в свое время на асме реализовал рюкзак, но, конечно, для одномерного раскроя.
24. logarifm 1116 24.12.15 23:31 Сейчас в теме
Честно - не очем вообще!
25. starik-2005 3031 24.12.15 23:33 Сейчас в теме
31. IvanovAV 131 05.08.17 22:11 Сейчас в теме
Подобный алгоритм мы используем в нашей самописной программе на 7.7 при автоматической загрузке автомобилей накладными.
Имеется массив автомобилей разной грузоподъемности, и массив накладных разного веса и объема, (которые едут в один район города) следовательно грузим самые тяжелые накладные в самые большие машины, затем цепочка по оставшимся машинам, в конце догружаем легкими накладными оставшееся место в машинах, получается идеальное распределение веса и объема. Точный код сейчас не вспомню, но принцип примерно такой.
32. wizard.ilmir02 122 18.06.19 20:22 Сейчас в теме
Добрый день! Подскажите как нужно модифицировать описанный алгоритм рюкзака, что бы его можно было использовать для выборки, в которых существуют повторяющиеся вещи с разным количеством?
33. starik-2005 3031 19.06.19 00:51 Сейчас в теме
(32) в принципе вместо цены - сумма, равная цене, умноженной на количество. Если цены нет - просто количество. Это, конечно, если я правильно понял смысл, ибо в последнее время народ ленится излагать мысли, а я ленюсь разбираться в плохо сформулированных вопросах.
34. wizard.ilmir02 122 19.06.19 06:51 Сейчас в теме
(33)извините, попытаюсь рассказать подробнее. Задача есть список деталей разной длинны, которые надо разложить на хлыст. Я попытался использовать ваш описанный алгоритм рюкзака 0-1 где подразумевается что количество разных деталей можно взять только один раз.
Например у нас есть детали : длинной 2, 4 , 3 ,5 и нужно разложить на хлыст размером 10. То можно легко построить таблицу где столбы будут длина от 1 до 10, а детали будут с ценой 1, а масса это будет длина детали. Теперь мне не понятно как использовать алгоритм рюкзака 0-1 для повторяющих деталей . Я нашёл статью где предлагается решение https://cs.stackexchange.com/questions/86531/transforming-a-bounded-knapsack-to-0-1-knapsack , просто дублировать в строчках повторяющие детали, но я не понял как считать стоимость для повторяющихся деталей, ведь стоимость детали одной длины я так понимаю будет одинаковой
35. starik-2005 3031 19.06.19 21:43 Сейчас в теме
(34)
ведь стоимость детали одной длины я так понимаю будет одинаковой
Да, алгоритм позволяет в исходных данных указывать одинаковый вес и цену - ведь в музее вполне могут быть предметы, одинаковые по ценности и весу. Просто на выходе Вам должно быть все-равно, какую деталь одинаковой длины брать. Их, в итоге, может оказаться и несколько.
36. DrBlack 23 04.12.20 13:42 Сейчас в теме
Могли бы уж и привести пример :)
Функция СортироватьВОбратнуюСторону(МассивЗначений)
	
	СписокЗначений = Новый СписокЗначений;
	СписокЗначений.ЗагрузитьЗначения(МассивЗначений);
	СписокЗначений.СортироватьПоЗначению(НаправлениеСортировки.Убыв);
	
	Возврат СписокЗначений.ВыгрузитьЗначения();
	
КонецФункции
Показать
starik-2005; +1 Ответить
37. spaceLama 21.01.23 23:49 Сейчас в теме
Можете ли как-то наставить на путь истинный? Возникла необходимость написать такую вещь для оптимального распила профилей для участка. Т.е. на входе может быть несколько кусков - и целых, и уже "покусанных", и на выходе нужно напилить детали разной длины. Критериев для оптимальности много, но это уже частности. Так вот, не сильно вдаваясь в математику и алгоритмы я начал с банального перебора. Работало до поры до времени, скорость была далека до идеала, но в целом пойдет. А вот на днях закинули пример, когда нужно напилить 90 деталей. И тут мой перебор начал ложить на лопатки сервер, т.к. съедал всю оперативу. Теперь начал уже в алгоритмы вдаваться, но пока как-то тяжело идет. "Жадный" понятен, но понятно также что он далек от оптимальности. Что насчет рюкзака? Вы обмолвились, что потребуется строить большие таблицы, но я, если честно, пока не очень хорошо понимаю как будет выглядеть таблица, если нужно еще и учитывать остатки. Это получается как-будто несколько рюкзаков? А как их связать потом? В общем, где-то в голове мысль крутится, а поймать её не выходит
38. starik-2005 3031 23.01.23 01:43 Сейчас в теме
(37)
что потребуется строить большие таблицы, но я, если честно, пока не очень хорошо понимаю как будет выглядеть таблица
Колонка - это единица размера. Если в сантиметрах, то количество колонок - это количество сантиметров в "рюкзаке".
Оставьте свое сообщение