Как найти количество вариантов получения числа из последовательности чисел?

Question

[Saymon_K]

Дана последовательность чисел. Например: 2 9 3 6 3 8 1 10 6 7.

Нужно узнать: сколькими способами можно образовать число, большее 8. При чем есть важное условие: если мы уже добились того, что комбинация больше 8 (3+3+3=9), то дополнять комбинацию новыми числами уже нельзя (3+3+3+5 - нельзя, ведь 3+3+3 - уже > 8).

Правильные ответ - 42, но я никак не могу понять как его добиться.

Я понимаю, что можно перебирать последовательность (2+9, 2+3+3, 2+...) и смотреть, больше 8 или нет, но это слишком долго. Я гуглил уже комбинаторику, но вот не нашел решение. Поэтому обратился сюда.

Подскажите формулу или толкните в нужном направлении.

Answer 1

[Армянское Радио]

Генерируете все сочетания, суммируете, сравниваете.

Гуглил он, называется...

Comments

[Saymon_K]

Так, по сути, это и есть перебор последовательности. Т.е. мы берем все возможные комбинации (а их ох как много) и суммируем, сравниваем. И это реально долго. Я думал есть какой-нибудь алгоритм решения таких задач.

[GavriKos]

Есть. Называется "Генетический алгоритм". Оптимизация перебора. Задача "расставить знаки в последовательности так, чтобы результат вычисления был n" решается ими быстро весьма. Почти ваш случай.

[Saymon_K]

GavriKos: Спасибо! Буду смотреть!

[Армянское Радио]

Saymon_K: Классическая упаковка рюкзака. От ее NP-полноты вы никуда не спрячетесь.

[Saymon_K]

Армянское Радио: Я не настолько хорошо как Вы) Не могли бы Вы объяснить поподробнее.

[Армянское Радио]

Saymon_K: Для данной задачи, как ее не верти и каким алгоритмом не решай, количество операций, потребных для ее решения, экспоненциально зависит от размера начального словаря.

[Mrrl]

Армянское Радио: При целых весах задача о рюкзаке решается за O(N*S), где S - объём рюкзака. Правда, при ограничении S < 10^9, N < 10^5 это мало спасает.

Answer 2

[Rsa97]

Напрашивается сортировка по возрастанию, затем рекурсивный перебор с отсечением по критерию.
2 | 9 | 3 | 6 | 3 | 8 | 1 | 10 | 6 | 7
Сортируем
1 | 2 | 3 | 3 | 6 | 6 | 7 | 8 | 9 | 10

функция перебор(numbers, result, summ) {
    пока numbers не пуст {
        current = numbers[0]; // первое число
        numbers = numbers[1..]; // остаток массива
        если summ+current > 8 
            вывести result, current;
        иначе
            перебор(numbers, [result | current], summ+current);
    }
}
перебор([1 | 2 | 3 | 3 | 6 | 6 | 7 | 8 | 9 | 10], [], 0);

Comments

[Saymon_K]

Спасибо! [result | current] - вот эту запись немного не понял. Можете объяснить?

[Rsa97]

Saymon_K: Добавить элемент current в конец массива result

[Saymon_K]

Rsa97: Благодарю!!!

Answer 3

[Mrrl]

Да, задача не имеет вообще ничего общего с тем, что вы написали вначале. Надо найти число подотрезков - то есть, фрагментов последовательности без пропусков. Ограничения "нельзя удлинять отрезок, если сумма достигла M+1" у них нет - они говорят только, что можно и не удлинять. То, что "воспользуемся модулем", не означает, что надо брать сумму модулей - иначе ответ был бы около 50. Вероятно, имеется в виду, что модуль суммы должен быть больше M (из примера этого понять нельзя, в нём нет отрезка с суммой меньше -8).
Могу сказать, что задача совсем непростая. Грубой силой она не решается (требуется N^2/2 сравнений, в секунду не уложитесь).
Я бы делал так. Взять массив частичных сумм (0, a0, a0+a1, ...). Потом сделать log_2(N) копий этого массива (занумерованных индексом k от 1 до log_2(N)), и в каждом из них отсортировать отрезки длиной 2^k. Для массива из задачи это будет выглядеть так:
S0=S[0]=[0,-2,7,10,16,19,27,26,36,30,37]
S[1]=[-2,0, 7,10, 16,19, 26,27, 30,36, 37]
S[2]=[-2,0,7,10, 16,19,26,27, 30,36,37]
S[3]=[-2,0,7,10,16,19,26,27, 30,36,37]
К сожалению, массивы S[1],S[2],S[3] оказались одинаковыми - это потому, что в примере мало отрицательных чисел.
Имея такие массивы, вы легко ответите на вопрос "сколько чисел в фрагменте массива S0[k+1]..S0[N] не принадлежат диапазону S0[k]-M .. S0[k]+M" (время - log(M)^2). Сумма таких ответов для всех k от 0 до M-1 и даст ответ на задачу. Полное время - M*log(M)^2.
UPD. Лучше бы они писали условие по-английски. Было бы не так стыдно за формулировку.

Comments

[Saymon_K]

Смотрите ниже

[Mrrl]

Исправил ответ в соответствии с условием.

[Saymon_K]

Ох, спасибо за ответ! Я в очередной раз не понял условие. Извините.

Answer 4

[Saymon_K]

В связи с тем, что появились недопонимания условия выкладываю оригинал (надо было это сделать сразу)

Comments

[Rsa97]

Это полностью меняет задачу. Раз надо выбрать подотрезок, то есть непрерывную часть исходной последовательности, то просто перебираем все начала/концы подпоследовательности

для i от 0 до N-1 {
    summ = 0;
    для j от i до N-1 {
        summ += A[j];
        если abs(summ) > M
            вывести A[i..j];
    }
}

[Saymon_K]

Rsa97: Значит это я неправильно задачу понял... Извините за тупость.

[Mrrl]

Rsa97: Не уложитесь в секунду.