Максимальная сумма подпоследовательности

Question

Учитывая массив целых чисел и пороговое значение, определите максимальную сумму любой подпоследовательности массива, которая меньше или равна пороговому значению. Для всех элементов, кроме не более 15, либо array[i] >= 2*array[j] или array[j] >=2*array[i], где j!=i.

threshold может составлять до 10 ^ 17, длина массива может составлять до60, а array[i] может быть до 10^16.

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

Answer 1

Эта проблема была тщательно разработана, чтобы на всех обычных подходах не хватало места. Вы должны использовать подсказку.

Шаг 1, затем отсортировать размер массива по убыванию и разделить его на 15 «странных» и цепочку элементов, таких как b1 >= 2*b2, b2 >= 2*b3 и т. Д. on.

Теперь для каждого из до 32768 подмножеств странных, попытайтесь выяснить, какое подмножество остальных подходит вам ближе всего. Однако вы можете использовать следующее наблюдение. Для любого элемента, который вы можете включить, либо он слишком велик, либо он должен быть включен. (Потому что, если вы не включите его, все остальное вместе даст вам меньшее число.) Это дает вам максимум 45 точек для принятия решения.