Итак, я нашел этот вопрос в topcoder:
Ваш друг Лукас дал вам последовательность натуральных чисел S.
Какое-то время вы двое играли в простую игру с S: Лукас выбрал бы
число, и вы должны были выбрать некоторые элементы S, так что сумма
все номера, которые вы выбрали, это номер, выбранный Лукасом. Например,
если S = {2,1,2,7} и Лукас выбрал число 11, вы бы ответили, что
2 + 2 + 7 = 11.
Лукас теперь хочет тебя обмануть, выбрав число Х так, чтобы
не будет действительного ответа. Например, если 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)) структуры данных должны быть достаточно быстрыми.
Так как же возможно, что 100000 * 20 даст нам максимально возможную сумму? Разве добавление всех элементов S не дало бы нам максимальную сумму?. Также я, кажется, вообще не понимаю всего решения. Как используются подмножества? Может кто-нибудь объяснить мне все решение? Я не получаю математику за этим. Я новичок в области динамического программирования.
Спасибо и извините, если я задал слишком много вопросов.