28
правок
Изменения
Нет описания правки
=== Реализация ===
Разделим наше множество на две части. Подсчитаем все подмножества из первой части и будем хранить их в массиве <tex> first </tex>. Отсортируем массив <tex> first </tex> по весу. Далее пройдемся по этому массиву и оставим только те подмножества, для которых не существует другого подмножества с меньшим весом и большей стоимостью. Очевидно, что подмножества, для которых существует другое, более легкое и одновременно более ценное подмножество, можно удалять.
Таким образом в массиве <tex> first </tex> мы имеем подмножества, отсортированные не только по весу, но и по стоимости. Тогда начнем перебирать все возможные комбинации вещей из второй половины и находить бинарным поиском удовлетворяющие нас нам подмножества из первой половине, хранящиеся в массиве <tex> first </tex>.
1. Сгенерируем '''bfs'''-ом все состояния, доступные из начала и конца за <tex> {n/2} </tex> или меньше ходов.
2. Найдем состоянийсостояния, которые достижимы из начала и из конца.
3. Найдем среди них наилучшее по сумме длин путей.
