gifts2017

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

Опубликовал Sergey Andreev (starik-2005) в раздел Программирование - Практика программирования

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

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

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

 

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

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

В принципе, код тут весьма простой и особых пояснений, полагаю, не требует, пишу его на псевдоязыке 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]);
КонецЕсли;

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

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

См. также

Подписаться Добавить вознаграждение
Комментарии
1. BigB (BigB) 23.12.15 21:27
(0) забористая у вас трава
Рязанский; fomstas; Shmell; bulpi; WhiteOwl; +5 Ответить
2. Андрей Карпов (karpik666) 24.12.15 07:41
Ошибка в таблице вместо 3200 должно быть 3300, и так дальше немного неверно.
starik-2005; +1 Ответить 2
3. Андрей Карпов (karpik666) 24.12.15 07:57
В заключении вы упомянули, что данную задачу можно применять для определения раскроя, как данный метод можно адаптировать к нему, к примеру задача: дано: макет самый простой - прямоугольный, но ширина и длина у каждого разная, есть ткань определенной ширины и длины, нужно максимально плотно раскроить ткань, чтобы оставалось как можно меньше обрезков, если учитывать площадь макета как ценность в данной задаче, то она не учитывает форму макета, так как по расчету можно поместить на ткань 4 макета, а фактически 3, но с кучей обрезков, так как по форме он не влезает.
4. Александр Шишкин (Шёпот теней) 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
bulpi; karpik666; +2 Ответить
5. Программулькин (Программулькин) 24.12.15 09:31
"пишу его на псевдоязыке 1С" - аФтора на кол!!
6. Sergey Andreev (starik-2005) 24.12.15 10:13
(2) karpik666, ну я ждал, когда кто-нибудь заметит ))) Рад, что хоть кто-то дочитал до конца! Но это ошибка в расчетах, а не в алгоритме.
7. Sergey Andreev (starik-2005) 24.12.15 10:14
(5) Программулькин, "псевдоязык" - это не то, что Вы подумали. Это некоторые функции, которых в языке нет. Т.е. с "мнимыми/ложными функциями".
8. Sergey Andreev (starik-2005) 24.12.15 11:55
(2) karpik666, исправил цифры. Теперь все ок?
9. Андрей Карпов (karpik666) 24.12.15 12:24
(8) starik-2005, почти, в комментариях теперь цифры расходятся с таблицей
Плюс в тексте теперь вы изменили 800 на 700, а в тексте нет
сумма = 1450 + 1500 + 800
10. Sergey Andreev (starik-2005) 24.12.15 12:46
(9) karpik666, чьйорд побьери, михаил светлоф ту-ту ))) Я тут статью отредактировал и нажал случайно "сохранить в черновик". В итоге с меня сняли 20 стартманей - пришлось писать в техподдержку, поэтому ну его нафиг редактировать эти статьи ))) Главное чтобы понятно было даже детям. А калькулятор я не догадался использовать - ведь основа статьи в описании принципа и коде, а не в правильной математике, подсчитанной в уме...
11. Евгений Ванжула (minimajack) 24.12.15 12:48
(10) starik-2005, да хрен ногу сломит...
в итоге оптимально должно быть 3200
10 /1000
20/1500
15/700
12. Sergey Andreev (starik-2005) 24.12.15 12:55
(11) minimajack, да, Вы правы. Просто я промахнулся с расчетами и вычислил в уме не совсем правильно, поэтому пришлось потом редактировать статью, но отредактировал я ее не до конца, ибо с удивлением обнаружил, что с меня за отмену публикации сняли 20 стартманей и поспешил вернуть все назад, не завершив редактирование до конца.

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

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

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

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

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

.. совсемУЖЖЖсовсем ...
16. Sergey Andreev (starik-2005) 24.12.15 13:20
(15) Шёпот теней, ну принципы этих алгоритмов в том, что создается "случайная" популяция - обычный рандом. Потом происходят случайные перестановки, приводящие к улучшению или ухудшению результата. Дальше все это повторяется до бесконечности. В 18 веке был придуман такой метод расчета числа pi с помощью "бросания иголки на пол" - это примерно та же тема.
17. Евгений Ванжула (minimajack) 24.12.15 13:20
(15) Шёпот теней, там используется фитнес функция которая выбирает лучших...скорее всего это и есть оптимизация
18. Алексей Роза (DoctorRoza) 24.12.15 13:52
+. чтобы окупить вложения
19. Sergey Andreev (starik-2005) 24.12.15 13:54
(18) DoctorRoza, да я особо не старался - ошибся вон в цифрах )))) Цель была в том, чтобы максимально просто все объяснить.
20. Алексей (artspeed) 24.12.15 16:24
Прочитав статью осознал свою никчемность.
Бывают же умные люди......
Простите за оффтоп.
21. Sergey Andreev (starik-2005) 24.12.15 17:13
(20) artspeed, да ну дадно Вам! Я сам с этимне за три минуты разобрался - просто интересно было.
22. Андрей Карпов (karpik666) 24.12.15 17:17
(20) artspeed, почитай статьи ildarovich вот его понимают вообще единицы. Кстати у него тоже была статья про алгоритм 3d упаковки, очень занимательная статья.
23. Sergey Andreev (starik-2005) 24.12.15 18:04
(22) karpik666, действительно у него много классных статей. Он, кстати, по большому счету использовал жажный алгоритм в языке запросо. Он вообще любит теорию и в принципе не сколько рабочие алгоритмы, сколько экстремальные красивые ситуации. Рекомендую!
24. Александр Хомяк (logarifm) 24.12.15 23:31
25. Sergey Andreev (starik-2005) 24.12.15 23:33
26. Вадим Миляев (PrinzOfMunchen) 25.12.15 06:00
(19) starik-2005, благодарю, хоть кто-то объяснил так, что наконец-то до конца всё дошло..)))
27. Sergey Andreev (starik-2005) 25.12.15 10:35
(26) PrinzOfMunchen, очень рад, что получилось объяснить на столько хорошо)))
28. Сергей (Che) Коцюра (CheBurator) 25.12.15 13:39
(22) я общался с Ильдаровичем. От его выкладок вообще офигеваю (сам вообще ни в зуб ногой). а 3d упаковка его пробовал у себя запустить, переписывался с ним в т.ч. - лажает. плохо упаковывает. пока что для упаковки лучше 3D-Packer - не видел, с его использованием у меня складской оператор вместимость ячеек считает по товарам.
29. Sergey Andreev (starik-2005) 25.12.15 13:43
(28) CheBurator, ну а что Вы хотите от жадного алгоритма, реализованного больше как "интересная фича" в языке запросов? Не будет он грамотно упаковывать никогда )))
30. Sergey Andreev (starik-2005) 25.12.15 13:48
(28) CheBurator, кстати, навеяло Вашим сообщением. Как-то в 80-х японцы поставили перед собой две задачи: создать тачку, не хуже, чем мерс - получился лексус. А вторая задача - создать процессор пятого поколения - с этим они обосрались (извините, но так и есть) по полной программе. Пока они пять лет мутили этот проц, продукция 4-го поколения от интела ушла так далеко вперед, что японцы должны были дружной командой сделать себе "ХарюКири" )))

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