Comments 54
NP-полную задачу можно решить полным перебором, да. В чем суть статьи?
По крайней мере в еще одном и достаточно простом варианте реализации этого перебора, разве нет?
Тем более, что тут не прям ПОЛНЫЙ перебор как минимум за счет сортировки по весу и ее обыгрывания в дальнейшем.
Ну как "не полный"? 100 элементов, вес каждого 1, вместимость рюкзака 10, стоимость не принципиальна. Алгоритм так или иначе переберет все 100! / (10! * 90!) = 17310309456440 возможных комбинаций.
Мне кажется, что вы все же что-то неправильно понимаете...
Ради любопытства написал такой тест с 50 элементами, с сотней запариваться не стал. Цена идет по возрастанию от элемента к элементу. Основная логика перебора - цикл в методе addSelectionResultForIndex. В сумме в нем прошло через 1225 итераций, например. Вся работа по формированию возможных наполнений в нем и выполняется. Это, правда, без учета логики подбора новой ветки.
Другое дело, что результат некорректный. Здесь, видимо, и есть слабое место - с множеством предметов одинакового веса я пока в целом проверял очень мало. Уже чувствую, где возможна проблема.
Подумаю, как поправить. За сценарий спасибо)
Ну а так - по крайней мере там, где вес не повторяется алгоритм справляется хорошо на первый взгляд.
Ну, вместимость 100000, веса от 9901 до 10000, если так нужны разные.
В любом случае думаю, что все не настолько печально)
Сперва поправлю проблему с повторяющимися весами.
Если еще интересно: разные веса, сгенерировано вот таким образом
Set<Item> items = new HashSet<>();for (int i = 1; i < 1000; i++) { items.add(new Item(String.valueOf(i), i, i));}
Вместимость рюкзака - 1999.
Решает за 200-300 мс. 498501 итераций основного цикла. Выдает цену 1999.
И всего веток-комбинаций сгенерировано 493055.
И пофиксить такое, возможно, тоже большого труда не составит. Уже крутится пара идей... Выявлять в отсортированном массиве такие группы повторяющихся весов, запоминать где-нибудь их начало и самую выгодную комбинацию внутри них (за счет сортировки по цене в рамках этой группы, когда вес равен 1 - это вообще ерунда, просто с последнего на вместимость рюкзака фетчим)... когда наткнулись на элемент такой группы - подтягиваем ветку оттуда... нужно будет попробовать. За сумбур извиняюсь)
Все, кажется, проблема решена.
Дополню статью.
Еще раз спасибо за кейс. Без вас, возможно, не обратил бы на это внимание.
.
А зачем в данном случае Backpack делать интерфейсом?
Привычка)
Как то очень сложно ваш код выглядит из за привычки писать в таком стиле. Это простая задача на рекурсию, но она реализована так, что логика трудно читается из-за энтерпрайз стиля. Такие задачи надо решать проще. А потом уже когда реализована логика решения, её обмазать хоть 10 слоями абстракций. Но не надо смешивать слои абстракции с логикой решения. Так мне кажется.
Итак, первый подвох уже найден) Как чувствовал, что что-то может пойти не так, когда множество элементов с повторяющимися весами.
На 50 элементах весом в 1 и стоимостью от 1 и возрастающей от элемента к элементу - такой кейс дает неправильный результат. На вместимости в 10 должно быть 495. В ближайшее время займусь фиксом этой проблемы. Уже есть несколько идей.
Я тоже как-то развлекался этим. Получилось так: https://github.com/samdark/sack
Можно развлекаться с любой NP-полной задачей, которая нравится, вроде можно всегда преобразовать одну в другую, в универе проходили.
Проблему с повторяющимися весами решил и, надеюсь, "креститься" не придется.
Дополнил статью и тест-кейсы. Минус один подвох, ждем выявления других)
Зачем использовать UUID для веток? Это не создаёт проблем с производительностью и памятью при больших наборах данных? Не проще ли работать с хэшами комбинаций?
Возможно и не стоит. Изначально это было введено, чтобы удалять ненужные ветки по шагу 5. Но т.к. я пришел к выводу, что шаг 5 - это, мягко говоря, непомерная трата ресурсов - это можно зарезать.
Спасибо за идею, действительно, уберу.
И ведь точно)) Большой тест теперь работает в 2 раза быстрее, как убрал ууидки.
А я и не знал, что такая прожорливая вещь.
Еще раз спасибо))
А если решение лежит в области наименее длинных комбинаций? Ну скажем 7 предметов из 1000?
Как я понимаю вы должны доказать, что Ваш алгоритм не отбрасывает верные варианты или делает это с очень низкой вероятностью. А до тех пор это очень спорная гипотеза.
P.S. Пока Вы работает с малыми количествами и без лимита по времени, так и сравните ваш результат с полным перебором для 10000 случайных выборок.
Да, вы правы. Надо будет попробовать.
Пока самый большой кейс был таким.
Set<Item> items = new HashSet<>();for (int i = 1; i < 1000; i++) { items.add(new Item(String.valueOf(i), i, i));}
С вместимостью 1999. Решало за 200-300 мс., 498501 итераций основного цикла, всего веток-комбинаций сгенерировано 493055. Показывало наборы с 1999 стоимостью. Конечно, стоит подсчитать сложность алгоритма, но пока лень, пусть остается на десерт.
Поменял вместимость на 10 - за 11 мс. подобрало решение с набором в стоимость 10. При такой генерации, судя по всему, наивысший профит будет равняться размерности. Если не ошибаюсь.
Конечно, алгоритм стоит гонять по разному. С придумыванием кейсов пока проблемы)
А, только сейчас до конца понял, в чем ваш вопрос...
"А если решение лежит в области наименее длинных комбинаций? Ну скажем 7 предметов из 1000?"
Да, по идее должно работать.
Алгоритм "Монте-Карло" называется или "Метод Научного Тыка" :) Но действительно работает и широко применяется. А его модификация MCTSU вообще чудеса творит.
https://ru.algorithmica.org/cs/combinatorial-optimization/annealing/ - наверное будет работать быстрее (при той же точности) или точнее (при том же времени)
Ну, лично я такое не пробовал. Звучит интересно)
Продолжаю свой крестовый поход по NP-полным задачам
Есть хорошая книга про NP-полные задачи и экспоненциальные алгоритмы: Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms
там есть все, от классических решений и стандартных оптимизаций до последних достижений науки (на 2010 год)
Алгоритм интересный, было бы интересно сравнить по скорости с динамическим программированием, которое работает за O(W*Nпредметов)
Например на задаче
for (int i = 0; i < 1000; i++) {
items.add(new Item(String.valueOf(i), 9000+i, i%10+1));
}
W := 500000
дин программирование у меня тупит 12 секунд (общая сумма 538). А сколько у Вас проверяемых узлов получится?
Спасибо)
У меня был похожий тест-кейс.Set<Item> items = new HashSet<>();for (int i = 1; i < 1000; i++) { items.add(new Item(String.valueOf(i), i, i));}
На вместимости 1999 решает за 200-300 мс. с 493055 созданных "веток". Показывало цену 1999. Нужно будет попробовать и на большей вместимости.
На данный момент понимаю, что алгоритм отчасти рабочий, но не на всех кейсах. Я явно теряю очень много потенциально-полезной информации, слишком тороплюсь убегать вперед на шаге 3.4, да и проверка только последней ветки - почему? В общем, слабые места есть и уже крутятся в голове заготовки идей, как это подправить. Будет видно, что получится.
С динамическим, думаю, тоже будет иметь смысл сравнить, если получится устранить все "подвохи".
Будет чем позаниматься завтра, в общем)
Да, ваш тест-кейс тоже хорош. Он успешно сломал мою реализацию branch&bounds - там вместо <= стояло < и она скатывалась в полный перебор если все удельные стоимости одинаковы. Однако после исправления оно находит в нем сумму всего за 169 проверенных узлов.
Но мой тест-кейс ломает и branch&bounds (как я понимаю, стоимость элементов слишком маленькая чтоб эвристика эффективно работала) и только динамическому программированию пофиг на особенности задачи и оно успешно проходит его.
А у вас есть ваша реализация на динамическом программировании?
Я просто продолжаю работу над алгоритмом (то, что описано в статье - в целом ерунда и полу-решение, способное дать лишь приближенный к оптимальному результат). Новая версия разруливает все подобранные мной кейсы, кроме, видимо, вашего. На вашем кейсе отрабатывает за 40-50 мс., но результат правда показывает 498, а не 538. Было бы очень полезно и интересно глянуть, как отрабатывает ваш вариант и в чем заключается отличие - возможно, удастся пофиксить проблему.
вот тут есть в том числе и на java:
https://rosettacode.org/wiki/Knapsack_problem/0-1
я проверял на том которое на Ruby, с виду логика та же.
Да, спасибо! В принципе, я уже нашел, тоже показывает 538.
Ну, пол-дела сделано, будем разбираться)
Ну что ж, полтора месяца работы - и я ПОЧТИ победил этот кейс))
int capacity = 500000;int h = 1000;List<Item> items = new ArrayList<>();
for (int i = 0; i < h; i++) {
items.add(new Item(String.valueOf(i), 9000 + i, i % 10 + 1));
}
Итого: 1.389.910 итераций основных циклов и 130 мс. моего алгоритма против 500.502.001 (надеюсь, правильно считаю) итераций и почти двух секунд на динамическом. Заветное 538 - есть. А если h=520 (набор дает тот же результат) - то количество итераций вообще 154.820.
Печально, что алгоритм пока не до конца точен. На некоторых шагах расхождения буквально на единицу, но они есть. Просто из-за одного нюанса работы, о котором знаю и думаю, как улучшить.
Все-таки клевый кейс вы дали, он надолго стал для меня "боссом-вертолетом". Спасибо еще раз!)
А вот на этом кейсе, например
Скрытый текст
List<Item> items = List.of(
new Item("1", 1, 10),
new Item("2", 3, 15),
new Item("3", 5, 21),
new Item("4", 8, 40),
new Item("5", 15, 55),
new Item("6", 24, 61),
new Item("7", 48, 35),
new Item("8", 56, 38),
new Item("9", 72, 72),
new Item("10", 93, 90),
new Item("11", 101, 101),
new Item("12", 125, 425),
new Item("13", 134, 25),
new Item("14", 147, 100),
new Item("15", 153, 240),
new Item("16", 161, 15),
new Item("17", 182, 150),
new Item("18", 250, 181),
new Item("19", 256, 203),
new Item("20", 278, 258),
new Item("21", 301, 111),
new Item("22", 304, 104),
new Item("23", 305, 1002),
new Item("24", 307, 20),
new Item("25", 310, 310),
new Item("26", 315, 315),
new Item("27", 328, 560),
new Item("28", 334, 770),
new Item("29", 561, 220),
new Item("30", 585, 185),
new Item("31", 604, 215),
new Item("32", 631, 205),
new Item("33", 657, 200),
new Item("34", 688, 150),
new Item("35", 691, 100),
new Item("36", 728, 1100),
new Item("37", 734, 160),
new Item("38", 905, 305),
new Item("39", 999, 310),
new Item("40", 1010, 350),
new Item("41", 1250, 450),
new Item("42", 1348, 480)
);
int capacity = 2000;показывает результат чуть хуже д.п.
91.573 основных итераций против 2.000 x 42 = 84.000, результат в обоих случаях 4217 (цена).
С другой стороны, я могу как угодно масштабировать веса и вместимость, просто дорисовывая нолики - и это никак не повлияет на работу нового алгоритма, количество итераций не поменяется ни на йоту. А вот д.п. улетит в космос, понятное дело.
Плюс ко всему - мой алгоритм, в теории, будет работать на любом типе данных для веса, целочисленный или вещественный - не важно. А вот с д.п. можно ли работать с вещественными весами, скажем - тут не уверен.
Блин, если бы не пара серьезных (но, возможно, таки решаемых) препятствий - возможно, это даже было бы чем-то прорывным. Но пока так)
Кстати, а вы не пробовали расширять этот кейс? 800.000 и 3000 элементов, например? Пытаюсь на д.п получить результат - но у меня по хипу отваливается) А алгоритм на удивление отрабатывает, емнип 848 показывает.
А чем плох такой вариант?
1) Сортируем по удельной цене по убыванию
2) Наполняем рюкзак. Когда встречаем предмет, который уже не "пролазит" по массе:
3) Берем из рюкзака минимальное n последних предметов так, чтобы:
вес этих предметов + оставшийся свободный вес >= вес текущего предмета
4) Сравниваем цены, чтобы решить, заменять ли их новым предметом
5) Считаем удельную цену замены с учетом оставшегося пустого места и кэшируем
6) Сравниваем удельную цену следующего не пролезающего предмета с кэшированным значением. Если она больше, повторяем с шага 3.
Мне кажется, такой вариант будет заметно быстрее и экономнее по памяти, но я совсем не математик, поэтому буду рад, если подсветите, если я что-то упускаю.
Задача о рюкзаке. Простое решение, но где-то должен быть подвох