Найти подмножество чисел

[AngryProj]

Подскажите, пожалуйста, как в заданной последовательности (массиве), найти подмножество чисел, сумма которых дает наибольшее число, являющееся степенью 2.
Непонятно именно то, как выделить подмножество.

[Stilet]

Ну я думаю перебирать двумя циклами.
Как вот пузырьковая сортировка делается, так и тут. Первый цикл с начала массива, второй с элемента первого цикла. Считать сумму, после второго цикла брать корень.

[Serge_Bliznykov]

думаю, двумя циклами не получится
Ведь нам нужно не два числа найти, а подмножество!

Что-то мне подсказывает, что тут ПОЛНЫЙ перебор всех вариантов понадобится.
А-ля "рюкзак"

[Stilet]

Может ты и прав...

[Poma][a]

За квадрат точно можно (ток если подмножество можно представить как непрерывную последовательность элементов массива. Мол с i-того по j-ый)

[Poma][a]

А кстати, Серж абсолютно прав.
Если под множеством понимать произвольный набор элементов массива. Будем использовать рюкзак.(тут его преобразовать и использовать только одномернный массив)
тогда получим массив, где элемент говорит можно ли набрать значение равное его индексу.

Кстати, можно подумать в сторону оптимизации по памяти для среднего случая, с помощью деревьев.

Но остается очень важный момент. Откуда начинать отсчет? Можно идти с конца.. только там вычислять индекс, высчитывать его, а потом идти вниз.
Если с начала, то можно идти с единицы, красиво проверять индексы в цикле, но мы пройдем весь массив

Что выбрать?

[Serge_Bliznykov]

а если под "подмножеством" понимать

как непрерывную последовательность элементов массива

тогда согласен, решение вполне двумя циклами (за квадрат) находится.


впрочем, что-то мне подсказывает, что автор темы уже потерял к ней интерес, поэтому что является "подмножеством" в данной задаче, мы, скорее всего, так и не узнаем!