Алгоритм. Найдите количество подмножеств, сумма которых находится в заданном диапазоне.

Это вопрос интервью. Мне задан массив чисел (возможны дубликаты, отрицательные числа) и нижний и верхний предел диапазона. Мне нужно найти количество возможных подмножеств, которые будут суммироваться с числом в пределах диапазона. Я посмотрел на вопрос, который ищет определенную сумму (find all subsets that sum to a particular value), но я не думаю, что пытаюсь сделать это, потому что каждое число в диапазоне - это самая эффективная вещь.Алгоритм. Найдите количество подмножеств, сумма которых находится в заданном диапазоне.

Диапазон может быть от -10^7 до 10^7.

источник

2016-12-27 Bharg

Кажется, ответ, на который вы ссылаетесь, может быть адаптирован. Вы, наверное, уже немного подумали, но вы не описываете, где вы застряли в своем вопросе, поэтому трудно предоставить полезную помощь, кроме как просто написать решение. –

Это явно NP-жесткий. Естественно, что подход с динамическим программированием является естественным. –

Эта проблема, по крайней мере, такая же сложная задача, как проблема суммирования подмножества, но когда сумма весов ограничена, я не знаю, остается ли она np-hard или становится доступной. –

Классический DP для суммы подмножества может быть изменен для решения этой проблемы, сохраняя счет вместо булевского индикатора для того, существует ли решение с данной суммой.

def subset_sum_count(lst, a, b): 
    sum_count = collections.Counter({0: 1}) 
    for x in lst: 
     for s, c in list(sum_count.items()): 
      sum_count[s + x] += c 
    return sum(c for (s, c) in sum_counts.items() if a <= s <= b)

источник

2016-12-27 18:27:07

Алгоритм. Найдите количество подмножеств, сумма которых находится в заданном диапазоне.

ответ

Смежные вопросы