Комментарии 51
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, с виду логика та же.
А чем плох такой вариант?
1) Сортируем по удельной цене по убыванию
2) Наполняем рюкзак. Когда встречаем предмет, который уже не "пролазит" по массе:
3) Берем из рюкзака минимальное n последних предметов так, чтобы:
вес этих предметов + оставшийся свободный вес >= вес текущего предмета
4) Сравниваем цены, чтобы решить, заменять ли их новым предметом
5) Считаем удельную цену замены с учетом оставшегося пустого места и кэшируем
6) Сравниваем удельную цену следующего не пролезающего предмета с кэшированным значением. Если она больше, повторяем с шага 3.
Мне кажется, такой вариант будет заметно быстрее и экономнее по памяти, но я совсем не математик, поэтому буду рад, если подсветите, если я что-то упускаю.
Задача о рюкзаке. Простое решение, но где-то должен быть подвох