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

Публикация № 437890

Разработка - Практика программирования

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

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

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

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

 

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

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

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

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

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

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

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

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

.. совсемУЖЖЖсовсем ...
16. starik-2005 2214 24.12.15 13:20 Сейчас в теме
(15) Шёпот теней, ну принципы этих алгоритмов в том, что создается "случайная" популяция - обычный рандом. Потом происходят случайные перестановки, приводящие к улучшению или ухудшению результата. Дальше все это повторяется до бесконечности. В 18 веке был придуман такой метод расчета числа pi с помощью "бросания иголки на пол" - это примерно та же тема.
17. minimajack 69 24.12.15 13:20 Сейчас в теме
(15) Шёпот теней, там используется фитнес функция которая выбирает лучших...скорее всего это и есть оптимизация
3. karpik666 2929 24.12.15 07:57 Сейчас в теме
В заключении вы упомянули, что данную задачу можно применять для определения раскроя, как данный метод можно адаптировать к нему, к примеру задача: дано: макет самый простой - прямоугольный, но ширина и длина у каждого разная, есть ткань определенной ширины и длины, нужно максимально плотно раскроить ткань, чтобы оставалось как можно меньше обрезков, если учитывать площадь макета как ценность в данной задаче, то она не учитывает форму макета, так как по расчету можно поместить на ткань 4 макета, а фактически 3, но с кучей обрезков, так как по форме он не влезает.
4. Шёпот теней 1766 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. Программулькин 290 24.12.15 09:31 Сейчас в теме
"пишу его на псевдоязыке 1С" - аФтора на кол!!
7. starik-2005 2214 24.12.15 10:14 Сейчас в теме
(5) Программулькин, "псевдоязык" - это не то, что Вы подумали. Это некоторые функции, которых в языке нет. Т.е. с "мнимыми/ложными функциями".
Артано; Дмитрий74Чел; +2 Ответить
18. DoctorRoza 24.12.15 13:52 Сейчас в теме
+. чтобы окупить вложения
19. starik-2005 2214 24.12.15 13:54 Сейчас в теме
(18) DoctorRoza, да я особо не старался - ошибся вон в цифрах )))) Цель была в том, чтобы максимально просто все объяснить.
26. PrinzOfMunchen 77 25.12.15 06:00 Сейчас в теме
(19) благодарю, хоть кто-то объяснил так, что наконец-то до конца всё дошло..)))
27. starik-2005 2214 25.12.15 10:35 Сейчас в теме
(26) PrinzOfMunchen, очень рад, что получилось объяснить на столько хорошо)))
20. artspeed 178 24.12.15 16:24 Сейчас в теме
Прочитав статью осознал свою никчемность.
Бывают же умные люди......
Простите за оффтоп.
21. starik-2005 2214 24.12.15 17:13 Сейчас в теме
(20) artspeed, да ну дадно Вам! Я сам с этимне за три минуты разобрался - просто интересно было.
22. karpik666 2929 24.12.15 17:17 Сейчас в теме
(20) artspeed, почитай статьи ildarovich вот его понимают вообще единицы. Кстати у него тоже была статья про алгоритм 3d упаковки, очень занимательная статья.
23. starik-2005 2214 24.12.15 18:04 Сейчас в теме
(22) karpik666, действительно у него много классных статей. Он, кстати, по большому счету использовал жажный алгоритм в языке запросо. Он вообще любит теорию и в принципе не сколько рабочие алгоритмы, сколько экстремальные красивые ситуации. Рекомендую!
28. CheBurator 3430 25.12.15 13:39 Сейчас в теме
(22) я общался с Ильдаровичем. От его выкладок вообще офигеваю (сам вообще ни в зуб ногой). а 3d упаковка его пробовал у себя запустить, переписывался с ним в т.ч. - лажает. плохо упаковывает. пока что для упаковки лучше 3D-Packer - не видел, с его использованием у меня складской оператор вместимость ячеек считает по товарам.
29. starik-2005 2214 25.12.15 13:43 Сейчас в теме
(28) CheBurator, ну а что Вы хотите от жадного алгоритма, реализованного больше как "интересная фича" в языке запросов? Не будет он грамотно упаковывать никогда )))
30. starik-2005 2214 25.12.15 13:48 Сейчас в теме
(28) CheBurator, кстати, навеяло Вашим сообщением. Как-то в 80-х японцы поставили перед собой две задачи: создать тачку, не хуже, чем мерс - получился лексус. А вторая задача - создать процессор пятого поколения - с этим они обосрались (извините, но так и есть) по полной программе. Пока они пять лет мутили этот проц, продукция 4-го поколения от интела ушла так далеко вперед, что японцы должны были дружной командой сделать себе "ХарюКири" )))

Как бы мысль в том, что миллиард операций в секунду делает сейчас ваш проц, а если на нем несколько ядер - и больше. Так вот периодически для не сильно большой выборки можно размещать что-то в чем-то даже методом полного перебора вариантов, находя лучший результат. Все упирается в скорость кода - 1С тут, конечно, совершенно не вариант. Я в свое время на асме реализовал рюкзак, но, конечно, для одномерного раскроя.
24. logarifm 1082 24.12.15 23:31 Сейчас в теме
25. starik-2005 2214 24.12.15 23:33 Сейчас в теме
31. IvanovAV 69 05.08.17 22:11 Сейчас в теме
Подобный алгоритм мы используем в нашей самописной программе на 7.7 при автоматической загрузке автомобилей накладными.
Имеется массив автомобилей разной грузоподъемности, и массив накладных разного веса и объема, (которые едут в один район города) следовательно грузим самые тяжелые накладные в самые большие машины, затем цепочка по оставшимся машинам, в конце догружаем легкими накладными оставшееся место в машинах, получается идеальное распределение веса и объема. Точный код сейчас не вспомню, но принцип примерно такой.
32. wizard.ilmir02 106 18.06.19 20:22 Сейчас в теме
Добрый день! Подскажите как нужно модифицировать описанный алгоритм рюкзака, что бы его можно было использовать для выборки, в которых существуют повторяющиеся вещи с разным количеством?
33. starik-2005 2214 19.06.19 00:51 Сейчас в теме
(32) в принципе вместо цены - сумма, равная цене, умноженной на количество. Если цены нет - просто количество. Это, конечно, если я правильно понял смысл, ибо в последнее время народ ленится излагать мысли, а я ленюсь разбираться в плохо сформулированных вопросах.
34. wizard.ilmir02 106 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 2214 19.06.19 21:43 Сейчас в теме
(34)
ведь стоимость детали одной длины я так понимаю будет одинаковой
Да, алгоритм позволяет в исходных данных указывать одинаковый вес и цену - ведь в музее вполне могут быть предметы, одинаковые по ценности и весу. Просто на выходе Вам должно быть все-равно, какую деталь одинаковой длины брать. Их, в итоге, может оказаться и несколько.
Оставьте свое сообщение

См. также

Использование программных перечислений, ч.1: строковые константы Промо

Практика программирования v8 1cv8.cf Бесплатно (free)

Часто ли у вас возникает необходимость в коде выполнять сравнение на строку?

10.12.2016    37612    unichkin    74    

«Варп-двигатель» для «среза последних»

Практика программирования Бесплатно (free)

Решение, позволяющее получить данные, аналогичные "срезу последних" на два порядка быстрее.

10.08.2020    2870    hobi    45    

1С: Документооборот, Data Science и Python

Документооборот и делопроизводство Математика и алгоритмы ДО Бесплатно (free)

В статье рассказывается о создании и обучении модели Data Science на языке Python и интеграции с системой 1С: Документооборот

04.08.2020    1695    Vaganov_Alexey    4    

Не спеша, эффективно и правильно – путь разработки. Часть 3. Практика

Практика программирования Бесплатно (free)

Черновой вариант книги Никиты Зайцева, a.k.a.WildHare. Разработкой на платформе 1С автор занимается с 1996-го года, специализация — большие и по-хорошему страшные системы. Квалификация “Эксперт”, несколько успешных проектов класса “сверхтяжелая”. Успешные проекты ЦКТП. Четыре года работал в самой “1С”, из них два с половиной архитектором и ведущим разработчиком облачной Технологии 1cFresh. Ну — и так далее. Не хвастовства ради, а понимания для. Текст написан не фантазером-теоретиком, а экспертом, у которого за плечами почти двадцать три года инженерной практики на больших проектах.

29.06.2020    9131    WildHare    33    

Вспомогательные инструкции в коде 1С Промо

Практика программирования v8 1cv8.cf Бесплатно (free)

Помогаем редактору кода 1С помогать нам писать и анализировать код.

15.10.2018    30703    tormozit    100    

Не спеша, эффективно и правильно – путь разработки. Часть 2. Теория

Практика программирования Бесплатно (free)

Черновой вариант книги Никиты Зайцева, a.k.a.WildHare. Разработкой на платформе 1С автор занимается с 1996-го года, специализация — большие и по-хорошему страшные системы. Квалификация “Эксперт”, несколько успешных проектов класса “сверхтяжелая”. Успешные проекты ЦКТП. Четыре года работал в самой “1С”, из них два с половиной архитектором и ведущим разработчиком облачной Технологии 1cFresh. Ну — и так далее. Не хвастовства ради, а понимания для. Текст написан не фантазером-теоретиком, а экспертом, у которого за плечами почти двадцать три года инженерной практики на больших проектах.

22.06.2020    10086    WildHare    23    

Не спеша, эффективно и правильно – путь разработки. Часть 1. Парадигма

Практика программирования Бесплатно (free)

Черновой вариант книги Никиты Зайцева, a.k.a.WildHare. Разработкой на платформе 1С автор занимается с 1996-го года, специализация — большие и по-хорошему страшные системы. Квалификация “Эксперт”, несколько успешных проектов класса “сверхтяжелая”. Успешные проекты ЦКТП. Четыре года работал в самой “1С”, из них два с половиной архитектором и ведущим разработчиком облачной Технологии 1cFresh. Ну — и так далее. Не хвастовства ради, а понимания для. Текст написан не фантазером-теоретиком, а экспертом, у которого за плечами почти двадцать три года инженерной практики на больших проектах.

15.06.2020    14408    WildHare    34    

Применение математических достижений в решении сложных задач бизнеса

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

Как правило, самые сложные задачи решаются с точки зрения математики очень легко. Но чтобы найти правильное решение, важно понять бизнес-цель, которую достигает эта задача. О практическом применении математических достижений для эффективного решения сложных задач бизнеса на конференции Infostart Event 2019 Inception рассказал Дмитрий Мишнов.

25.05.2020    3460    Mishnov    17    

Оформление и рефакторинг сложных логических выражений Промо

Практика программирования v8 Россия Бесплатно (free)

В сложных логических выражениях нередко самому автору спустя какое-то время тяжело разобраться, не говоря уже о других программистах. Предлагаемая методика позволяет повысить наглядность таких выражений путем оформления в виде И-ИЛИ дерева и одновременно выполнять их рефакторинг.

20.09.2012    78298    tormozit    131    

JSON в запросах DaJet QL

Практика программирования Бесплатно (free)

Практические примеры работы с JSON непосредственно в языке запросов. Перенос курсов валют между УТ и БП. Требуется SQL Server 2016 и выше.

24.04.2020    3844    zhichkin    6    

Визионное программирование

Практика программирования Бесплатно (free)

Новый способ программирования и его практическая демонстрация.

22.04.2020    4582    mkalimulin    111    

Улучшение пооперационного планирования в 1С:ERP 2.4 внешними средствами

Математика и алгоритмы Производительность и оптимизация (HighLoad) Бесплатно (free)

Задача построения оптимального производственного расписания требует сравнения тысяч и десятков тысяч вариантов. Выполнять такие вычисления средствами платформы 1С Предприятие нецелесообразно. Как реализовать пооперационное планирование с использованием генетических алгоритмов и параллельных вычислений в докладе на конференции Infostart Event 2019 Inception рассказал генеральный директор компании «ИНТЕХ» Сергей Сафаров.

02.03.2020    5421    ildarovich    7    

Запись значения в поле ввода/формы со срабатыванием события ПриИзменении Промо

Практика программирования v8 1cv8.cf Россия Бесплатно (free)

Иногда возникает необходимость после записи значения в какое либо поле ввода/формы вызвать для него обработчик события ПриИзменении, а о вызове самого события приходится только мечтать. В этой статье приводится программный способ вызова этого события.

11.07.2007    48772    tormozit    41    

Использование машинного обучения для решения инцидентов. Практическое применение

Практика программирования Бесплатно (free)

Продолжаю (и заканчиваю) тему с автоматическим решением инцидентов. Перейдем от теории к практике.

25.02.2020    4253    Repich    9    

Использование машинного обучения для решения инцидентов

Практика программирования Бесплатно (free)

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

18.02.2020    6926    Repich    17    

Часовой на страже логов

Практика программирования Инструментарий разработчика Бесплатно (free)

При поддержке решений, которые установлены у большого количества пользователей на различных системах, очень важно вовремя получать подробную информацию о возникших проблемах. О том, как собирать логи и анализировать полученные данные в трекере ошибок Sentry на конференции Infostart Event 2019 Inception рассказал Андрей Крапивин.

13.01.2020    6913    Scorpion4eg    8    

Как сделать из &НаКлиентеНаСервереБезКонтекста почти &НаКлиентеНаСервере Промо

Практика программирования v8 1cv8.cf Россия Бесплатно (free)

Как сделать метод формы, доступный на клиенте и на сервере одновременно, и сохранить при этом удобство разработки

10.09.2017    45156    tormozit    74    

Приватный блокчейн и 1С популярно

Практика программирования Блокчейн Бесплатно (free)

Две предыдущие публикации на эту тему были сфокусированы преимущественно на технической стороне вопроса. Кроме того, их содержание оказалось понятным не каждому специалисту. В этой статье я постараюсь обяснить для всех и, что говорится, «на пальцах»: что такое приватный блокчейн, когда и зачем его следует применять и на что обратить внимание при использовании этой технологии в 1С.

02.09.2019    6170    mkalimulin    140    

Кодогенерация и метагенерация в 1С

Практика программирования Инструментарий разработчика Бесплатно (free)

В своем докладе на конференции INFOSTART EVENT 2018 EDUCATION Дмитрий Белозеров рассказал о разработке инструмента, позволяющего программно работать с метаданными 1С и писать скрипты для выполнения тех же действий, которые выполняет разработчик в конфигураторе –  с какими сложностями и нюансами пришлось столкнуться, и что получилось в итоге.

26.08.2019    9093    kirovsbis    28    

Интеграция сценарного тестирования в процесс разработки

Практика программирования Инструментарий разработчика Бесплатно (free)

Разработчик системы «Тестер» Дмитрий Решитко в своем докладе на конференции INFOSTART EVENT 2018 EDUCATION показывает, что процесс тестирования можно очень плотно интегрировать в процесс разработки, что внедрение тестирования – это возможность развития программиста как такового, позволяющая ему упорядочивать ход мыслей и оставаться «в фокусе». Навыки построения процесса кодирования на стыке с тестированием сокращают время на концентрацию, освобождают от страха перед изменениями и улучшают память разработчика.

08.07.2019    9273    grumagargler    7    

Развитие 1С программиста Промо

Практика программирования Личная эффективность Бесплатно (free)

Делюсь своим опытом и видением развития 1С программиста.

17.10.2018    21190    pashamak    62    

Управляй качеством кода 1С с помощью SonarQube

Практика программирования Россия Бесплатно (free)

Управляй техническом долгом проектов 1С с помощью SonarQube. В статье рассматривается пример применения SonarQube при разработке.

07.07.2019    40940    olegtymko    231    

Выдержки из книги Чистый код

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

Недавно я прочитал книгу "Чистый код" Роберта Мартина (Robert Cecil Martin). В ней описываются принципы организации и форматирование исходного кода программы так, чтобы в дальнейшем было легко поддерживать такой код. Эта книга является библией для многих программистов, но вот в среде программистов 1С, к сожалению, не очень распространено чтение подобной фундаментальной литературы. Книга более 400 страниц и так много порой лениво читать, да и времени всегда не хватает. По этому я решил выделить в виде цитирования по разделам самые важные моменты. А также снабдил текст своими примерами кода.

16.05.2019    10817    FreeArcher    105    

Выгрузка документа по условию

Практика программирования Разработка v8 Бесплатно (free)

Что делать, если документы нужно выгружать не все подряд, а по какому-то фильтру: статусу, дате, набору условий... А что если он соответствовал этим условиям, а потом перестал? А если потом опять начал? Такие ситуации заставили попотеть не одного программиста.

25.04.2019    16147    m-rv    2    

Как сделать запрос на изменение данных Промо

Практика программирования v8 v8::Запросы 1cv8.cf Бесплатно (free)

В статье приведены особенности внутренней архитектуры и примеры работы с расширением языка запросов 1С.

01.06.2018    30982    m-rv    21    

Как прикрутить ГУИД к регистру сведений

Практика программирования Перенос данных из 1C8 в 1C8 Разработка v8 Бесплатно (free)

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

16.04.2019    20438    m-rv    17    

О времени и 1С

Практика программирования Разработка Бесплатно (free)

Основы и особенности работы со временем в 1С. Как избавиться от боли при работе в разных часовых поясах. Что такое момент времени. И другое.

01.04.2019    36448    YPermitin    61    

Метод формирования движений в типовых регистрах нетиповыми регистраторами Промо

Практика программирования v8 1cv8.cf Бесплатно (free)

Вариант решения задач с проведением по типовым регистрам нетиповыми регистраторами. Зачем - чтобы при сравнении конфигурации не обращать внимание на свойства регистров и исключить вероятность допущения горькой оплошности при обновлении информационных баз, заменив типы регистраторов основной конфигурации типами конфигурации поставщика. Для программных продуктов, имеющих в своем составе метаданных документ "Корректировка регистров"("Корректировка записей регистров").

05.12.2017    28384    itriot11    34    

Пример создания bridge (http api - tcp) для ККТ "Касса №1" ("К1-Ф")

Практика программирования ККМ Кассовые операции Кассовые операции Разработка Россия Бесплатно (free)

Пример создания bridge (http api - tcp) для ККТ "Касса №1" ("К1-Ф"). Данная статья будет полезна интеграторам, программистам, тем кто работает (интегрирует, разрабатывает) различное ТО либо железки. Версия и релиз технологической платформы не имеет значения.

17.03.2019    6625    dmarenin    1    

Быстрее чем INSERT! BULK-операции и примеры использования

Производительность и оптимизация (HighLoad) Практика программирования Внешние источники данных Перенос данных из 1C8 в 1C8 Разработка Бесплатно (free)

Microsoft SQL Server поддерживает так называемые BULK-операции, используемые для быстрого изменения больших объемов данных в базе. В статье пойдет речь о практических примерах их использования. Все примеры сделаны в контексте платформы 1С (а как иначе).

09.03.2019    25009    YPermitin    40    

Как писать понятные коммиты

Практика программирования Разработка Россия Бесплатно (free)

Как писать сообщения коммитов так, чтобы потом не было мучительно больно.

06.03.2019    12848    Scorpion4eg    35    

Использование классов .Net в 1С для новичков Промо

Практика программирования Разработка внешних компонент Универсальные функции v7.7 v8 Бесплатно (free)

Руководство для новичков. Написав статью http://infostart.ru/public/238584/, я понял, что многие не понимают того, что написано. Поэтому в этой статье постараюсь более подробно остановиться на азах и без кода на вражеском языке (C#)

27.01.2016    76817    Serginio    108    

Что такое алгоритм?

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

Как ответить на этот вопрос и не попасть пальцем в небо.

25.02.2019    8923    mkalimulin    274    

Подготовка ребёнка к ЕГЭ по информатике. Часть шестнадцатая

Практика программирования Разработка Бесплатно (free)

Поиск выигрышной стратегии, завершающая статья.

22.02.2019    5777    vasilev2015    0    

Автоматические и управляемые блокировки применительно к типовым конфигурациям 1С Промо

Математика и алгоритмы Практика программирования v8 v8::blocking 1cv8.cf Бесплатно (free)

Основные принципы работы с режимами автоматических и управляемых блокировок в 1С Предприятие 8. Теория и применение в типовых конфигурациях: БП, УТ, ЕРП

10.11.2018    35322    ids79    40    

Подготовка ребёнка к ЕГЭ по информатике. Часть тринадцатая

Практика программирования Разработка Бесплатно (free)

Исправление ошибок в программе, часть вторая.

20.02.2019    5797    vasilev2015    3    

Тестер: частые вопросы Промо

Практика программирования v8 Бесплатно (free)

Ошибкам бой - тесты норма жизни!

25.07.2018    29436    grumagargler    28    

Подготовка ребёнка к ЕГЭ по информатике. Часть восьмая

Практика программирования Разработка Бесплатно (free)

Шифрование и дешифрование информации. Закон Фано

05.02.2019    5642    vasilev2015    1    

Расширяем свой багаж

Практика программирования Разработка Бесплатно (free)

Алгоритм решения возможной нетиповой задачи на собеседовании.

29.01.2019    6399    scientes    15    

Криптовалюты, а также иные взгляды на природу денег в терминах 1С

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

Это отчасти полемическая статья. Я задумал написать ее как ответ на другую хорошую статью о криптовалютах. Хотелось поспорить с некоторыми утверждениями автора, а ещё больше с некоторыми комментариями. А чтобы текст был более понятным для местной аудитории, я решил использовать, где только возможно, терминологию и практику 1С.

28.01.2019    6248    mkalimulin    89