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

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

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

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

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

В принципе, код тут весьма простой и особых пояснений, полагаю, не требует, пишу его на псевдоязыке 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. Также ограничим грузоподъемность грабителя пятьюдесятью килограммами. В итоге получим такую табличку:

Как, собственно, мы построили эту таблицу? Все достаточно просто: в цикле для каждой вещи мы заполняли стоимость. В колонках у нас масса (я взял кратно 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]);
КонецЕсли;

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

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