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

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

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

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

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

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

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

 

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

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

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

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

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

67

Специальные предложения

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

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

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

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

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

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

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

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

См. также

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

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

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

02.09.2019    1497    mkalimulin    140       

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

Статья Программист Нет файла Бесплатно (free) Практика программирования Математика и алгоритмы Разработка

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

26.08.2019    3965    kirovsbis    28       

Запрос SQL для нахождения самого большого простого числа меньше заданного 6

Статья Программист Нет файла Windows Бесплатно (free) Математика и алгоритмы

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

16.08.2019    1212    alex_bitti    18       

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

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

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

08.07.2019    4403    grumagargler    7       

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

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

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

07.07.2019    16044    olegtymko    191       

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

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

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

16.05.2019    5578    FreeArcher    82       

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

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

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

25.04.2019    4788    m-rv    2       

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

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

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

16.04.2019    7316    m-rv    16       

О времени и 1С 206

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

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

01.04.2019    15193    YPermitin    58       

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

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

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

17.03.2019    2959    dmarenin    0       

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

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

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

09.03.2019    9722    YPermitin    38       

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

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

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

06.03.2019    7815    Scorpion4eg    34       

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

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

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

25.02.2019    2913    mkalimulin    272       

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

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

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

29.01.2019    3288    scientes    15       

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

Статья no Нет файла Бесплатно (free) Математика и алгоритмы

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

28.01.2019    3586    mkalimulin    89       

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

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

Решение систем логических уравнений повышенного уровня сложности.

25.01.2019    3054    vasilev2015    0       

Как писать код? Технологии древних цивилизаций, или все новое - это хорошо забытое старое 70

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

Все современные технологии - это развитие и доведение до ума (или маразма) древних идей. За последнее время не придумали ничего нового - все, что мы видим, было придумано тысячи лет назад. Не является исключением и программирование, которое в сути своей является переводом с языка условностей технического задания или заявки пользователя в формализованный и абсолютно точный язык математической логики. А логику придумали (по крайней мере первыми опубликовались в ведущих научных журналах) еще древние греки.

23.01.2019    8596    starik-2005    43       

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

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

Примеры на Паскале. Если сам родитель* - поддержи ! Если сам водила - посигналь !

19.01.2019    3296    vasilev2015    0       

Подготовка к ЕГЭ сына - школьника (по информатике) 9

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

Примеры на Паскале. Если сам отец - поддержи ! Если сам водила - посигналь !

17.01.2019    3799    vasilev2015    50       

Многоязычное программирование: создание систем с использованием нескольких языков 17

Статья Программист Нет файла Россия Бесплатно (free) Математика и алгоритмы

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

09.01.2019    5591    kalyaka    33       

Размышления о хороших практиках, навеянные одной статьей 12

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

Прочитал статью "Ректальное программирование: основы для практикующих 1С-программистов". Статья очень хорошая и своевременная. Но у меня возникло некоторое сомнение. А достаточно ли автор любит и понимает предмет, о котором пишет? Насколько богат его опыт ректального программирования и занимался ли он им вообще? Как человек обладающий многолетним опытом РП, я решил представить вам необходимые дополнения к статье.

21.12.2018    4416    mkalimulin    61       

Ректальное программирование: основы для практикующих 1С-программистов 294

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

Одной из самых популярных и зарекомендовавших себя методологий программирования в 1С является так называемое ректальное программирование. Редкий проект внедрения и сопровождения учётных систем на платформе 1С обходится без его использования. Зачастую без знания данной методологии программистам даже бывает сложно найти работу в сфере 1С, потому что работодатели, особенно фирмы-франчайзи, в основном отдают предпочтение классическим, зарекомендовавшим себя методикам, а не новомодным заграничным веяниям.

19.12.2018    30557    for_sale    340       

Быстрая отладка экранных форм документов и справочников 19

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

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

18.12.2018    4582    milkers    19       

1С + asterisk (автоматический обзвон) часть 1 38

Статья Системный администратор Программист Нет файла Россия Бесплатно (free) Практика программирования WEB Телефония, SIP

Пример реализации автообзвона (с обработкой ответа на отвечающей стороне) с использованием ami asterisk. Данная статья может быть полезна программистам, интеграторам, администраторам. Версия и релиз технологической платформы не имеет значения.

29.11.2018    7212    dmarenin    9       

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

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

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

17.10.2018    13521    pashamak    62       

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

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

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

15.10.2018    20408    tormozit    100       

Записки про metadata.js 53

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

Отличительные особенности разработки на metadata.js

31.07.2018    9103    1c-intelligence    59       

Учебный курс. Повышение качества разработки. Ошибки программы 97

Статья Программист Нет файла Бесплатно (free) Практика программирования Математика и алгоритмы Рефакторинг и качество кода

Учебный курс по теории и практике программирования. Бесплатно. В виде структурированного текста. Лекции № 3,4,5. Эти лекции посвящены ошибкам программ, их классификации и способам исправления

10.07.2018    15767    Артано    92       

Автоматизируй это! 148

Статья Системный администратор Программист Нет файла Бесплатно (free) Практика программирования

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

02.07.2018    16102    Tavalik    12       

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

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

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

01.06.2018    21144    m-rv    21       

Що там у них в Java 19

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

Развенчание мифа о тяжёлой жизни не 1С программистов на примере создания веб сервиса редактирования таблички с использованием framework spring в Java.

24.05.2018    9171    van_za    62       

Учебный курс. Повышение качества разработки. Вводная лекция, часть 2 49

Статья Программист Нет файла Бесплатно (free) Практика программирования Математика и алгоритмы

Учебный курс по теории и практике программирования. Бесплатно. В виде структурированного текста. Лекция №2. Эта лекция посвящена абстракциям, их свойствами и практическому применению в рамках классических парадигм программирования.

24.05.2018    10680    Артано    36       

Учебный курс. Повышение качества разработки. Вводная лекция 116

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

Учебный курс по теории и практике программирования. Бесплатно. В виде структурированного текста.

10.05.2018    15549    Артано    51