Расчет лимитов в динамическом программировании

Question

Я нашел этот вопрос в topcoder:

Ваш друг Лукас дал вам последовательность натуральных чисел S.

Некоторое время вы двое играли в простую игру с S:Лукас выберет число, и вам нужно было выбрать некоторые элементы S, чтобы сумма всех выбранных вами чисел была числом, выбранным Лукасом.Например, если S = ​​{2,1,2,7} и Лукас выбрал число 11, вы бы ответили, что 2 + 2 + 7 = 11.

Теперь Лукас хочет обмануть вас, выбрав числоX такой, что не будет действительного ответа.Например, если S = ​​{2,1,2,7}, невозможно выбрать элементы S, которые суммируют до 6.

Вам дан int [] S. Найдите наименьшее положительное числоцелое число X, которое нельзя получить как сумму некоторых (возможно, всех) элементов S.

Ограничения: - S будет содержать от 1 до 20 элементов включительно.- Каждый элемент S будет между 1 и 100 000 включительно.

Но в редакционном решении было написано:

Как насчет поиска наименьшей невозможной суммы?Итак, мы можем попробовать следующий наивный алгоритм: сначала попробуйте с x = 1, если это неверная сумма (найденная с использованием методов из предыдущего раздела), затем мы можем вернуть x, иначе мы увеличиваем x и пытаемся снова, иснова, пока мы не найдем наименьшее число, которое не является действительной суммой.

Найдем верхнюю границу для числа итераций, количество значений x, которое нам нужно будет попробовать, прежде чем мы найдем результат.Прежде всего, максимально возможная сумма в этой задаче составляет 100000 * 20 (все числа - максимум 100000), это означает, что 100000 * 20 + 1 не будет невозможным значением.Мы можем быть уверены, что потребуется не более 2000001 шагов.

Насколько хороша эта верхняя граница?Если бы у нас было 100000 в каждом из 20 чисел, 1 не была бы возможной суммой.Так что на самом деле нам нужна одна итерация в этом случае.Если мы хотим, чтобы 1 была возможной суммой, у нас должно быть 1 в начальных элементах.Затем нам нужно 2 (иначе нам понадобится только 2 итерации), затем 4 (3 можно найти, сложив 1 + 2), затем 8 (числа от 5 до 7 можно найти, добавив некоторые из первых 3 степенейдва), затем 16, 32, .... Оказывается, что со степенями 2 мы можем легко сделать входные данные, которые требуют много итераций.С первыми 17 степенями от двух мы можем покрыть до первых 262143 целых чисел.Это должно быть хорошей оценкой для наибольшего числа.(Мы не можем использовать 2 ^ 18 во входных данных, меньше 100000).

До 262143 раз нам нужно запросить, находится ли число x в наборе возможных сумм.Мы можем просто использовать логический массив здесь.Похоже, что даже структуры данных O (log (n)) должны быть достаточно быстрыми.

Я понял первый абзац.Но после этого они объяснили что-то вроде «Насколько хороша эта верхняя граница? ...».Я не мог понять этот пункт.Как они пришли к тому, что нам нужно запросить 262143 раза, если число x находится в наборе возможных сумм?

Я новичок в динамическом программировании, и поэтому было бы здорово, если бы кто-то мог объяснить этомне.

Спасибо.

Answer 1

Идея заключается в следующем:

Если входная последовательность содержит первые k степени двух: 2^0, 2^1, ... 2^(k-1), то сумма может быть любым целым числом от 0 до (2^k) - 1.Поскольку наибольшая степень двух, которые могут появиться в последовательности, равна 2^17, наибольшая сумма, которую вы можете построить из 18 чисел, равна 2^18 - 1=262,143.Если бы отсутствовала степень двойки, была бы меньшая сумма, которую было бы невозможно получить.

Однако отсутствует утверждение о том, что в последовательности может быть еще 2 числа (не более 20).Из этих двух чисел вы можете повторить один и тот же процесс.Следовательно, максимальное количество проверяемых на самом деле (2^18) - 1 + (2^2) - 1.

Вы можете удивиться, почему мы используем силы двух, а не любые другие силы.Причина заключается в двоичном выборе, который мы выполняем для чисел во входной последовательности.Либо мы добавляем число к сумме, либо нет.Итак, если мы представим этот выбор для числа ni как переменную выбора si (0 или 1), то возможная сумма будет:

s = s0 * n0 + s1 * n1 + s2 * n2 + ...

Теперь, если мы выберем niбыть степенями двух ni = 2^i, тогда:

s = s0 * 2^0 + s1 * 2^1 + s2 * 2^2 + ...
  = sum si * 2^i

Это эквивалентно двоичным представлениям чисел (см. Позиционное обозначение ).По определению, разные варианты выбора переменных будут давать разные суммы.Следовательно, число возможных сумм максимально, выбирая степени два во входной последовательности.