Не все не читают теги))

Дам маленькую подсказку. O(N² * 2^N), но на практике всё гораздо меньше.

Можно за O(2ⁿ·n). Вообще основная стандартная идея такая. Будем делать динамику по множеству взятых объектов. Хранить множество можно в виде числа. Если представить число в двоичном виде, то можно сказать, что элементы, в разрядах которых стоят единицы, входят в множество, кодируемое данным числом.

Переход в динамике — возьмем один или два предмета. Как взять один ---понятно: переберем удаляемый элемент, посмотрим, что мы насчитали для множества, где этот элемент отсутствует и прибавим квадрат расстояния от него до сумки. Если мы хотим O(2ⁿ·n²), то с двумя можно делать примерно то же самое, перебрать их, посмотреть ответ для множества без них и прибавить расстояние, которое нужно пройти, чтобы их собрать (нужно сложить расстояние между этими предметами и расстояния от каждого предмета до сумки).

Теперь, чтобы стало O(2ⁿ·n), надо понять, что всегда нужно убирать предмет с самым маленьким номером. То есть, останется перебрать только один предмет из пары. Почему это так? Потому что порядок взятия не важен и когда-то нам в любом случае придется брать этот предмет. Если мы возьмем его сейчас, мы ничего не испортим.

Код: 2039949