Обобщенная задача о целевой сумме

Question

Учитывая целое число x и несортированный массив целых чисел, опишите алгоритм, чтобы определить, складываются ли два числа из числа x.(В этом случае хеш-таблицы не допускаются). Решение:

Сортировка массива.Затем следите за двумя указателями в массиве, один в начале и один в конце.Когда сумма текущих двух целых чисел меньше x, перемещайте первый указатель вперед, а всякий раз, когда сумма больше x, перемещайте второй указатель назад.Если вы не можете найти два числа, которые добавляются к x до того, как один из указателей встретится, то не существует пары целых чисел, которые суммируют с x.Это решение занимает O (n log n) времени, потому что мы сортируем числа.

Можем ли мы получить обобщенное решение для k целых чисел.Скажем выше проблема для k=2.Теперь я хочу найти 3 целое число с target sum и т. Д.

Answer 1

Просто чтобы установить верхнюю границу этого ... для фиксированного k, проблема всегда в P (полиномиальной по размеру списка чисел, n, в любом случае) и может быть решена простым O n ^ k) алгоритм: сгенерируйте k-множества (их C (n, k)) и проверьте их. Для случая k = 2 это соответствует генерации всех n (n + 1) / 2 двух множеств и проверке их.

Если вместо этого взять k <= n, эта задача эквивалентна проблеме суммы подмножеств, следовательно, NP-полной. </p>

Обратите внимание, что они представляют строгие верхние границы сложности ... для k = 2 вы нашли алгоритм O (n log n), и подход может быть обобщен до более высокого k.

Edit2: убраны некоторые более узкие границы, так как кажется, что моя конструкция была неправильной. Извините, что облажался. Реквизит spinning_plate за честность.

Answer 2

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

1. Требуется различный набор целых чисел (без повторов)
2. Всякий раз, когда sum = x, я сохраняю целые числа, удовлетворяющие sum = x, и продолжаю, чтобы получить все кортежицелых чисел, удовлетворяющих сумме = x

Раздел A

k = 3 и x = сумма

Сортировка массива в порядке возрастания.
Поместите first_pointer в первое целое число, а second_pointer во второе целое число (т.е. рядом с первым указателем).
Поместите third_pointer в последнее целое число.

1. Рассчитать сумму = first_pointer + second_pointer + third_pointer.
2. если сумма
3. , если сумма> x, а затем третий_поинтер-- Повторите шаг 1.
4. Повторите шаги с 1 по 3, пока секунда-указатель> = третья-точкато есть указатели встречаются.
5. first_pointer ++;second_pointer = first_pointer + 1;third_pointer = последнее целое число, т.е. сместить first_pointer на один шаг (справа) и поместить second_pointer рядом с первым указателем, вернуть третий указатель на последнее целое число.
6. Повторите шаги с 1 по 5 до 5-го шага second_pointer = third_pointer.
7. Если вы дойдете до этого места, не найдя никакой суммы = x, тогда не будет никакого решения (я могу ошибаться, но я не вижу никакой другой возможности.)

Раздел B

для k = 4 и x = сумма

Сортировать массив в порядке возрастания.
Поместить первые два указателя какв Раздел A .
Поместите третий и четвертый в последние два целых числа, то есть третий указатель = second_last_integer и четвертый_поинтер = last_integer.

1. Аналогично РазделШаг 1 сумма = указатель (1-й + 2-й + 3-й + 4-й)
2. Аналогично Раздел A Шаг 2
3. ( Это отличается ) если сумма> x, то четвертая_точка--
4. Аналогично Раздел A Шаг 4
5. ( теперь совсем другой ) Я будуразделите это как 5.a и 5.b для ясности
   5.a Эта часть похожа на Section A в том смысле, что вы будете перемещать первый и второй указатели, оставляя их рядом друг с другом иповторяя шаги с 1 по 4 из Раздел B
   5.b Если вы еще не нашли сумму third_pointer--;third_pointer = third_pointer-1 и повторите шаги с 1 по 4 и 5.a
6. Повторите 5.b до second_pointer = third_pointer.

Если вы дошли до здесь без какой-либо суммы = x, то решения не существует // standard-disclaimer

Раздел C

(У меня действительно не хватает места на экране, так как я не вижу предварительный просмотр того, что пишу. Поэтому я буду коротким и оставлю это на ваше усмотрение)
для любых k и x = сумма

Сортировка массива в порядке возрастания.
Разместите первые int (k / 2) указатели в начале.
Поместите остальные k-int (k / 2) указатели в конце.

1. Рассчитать сумму = сигма (к).
2. если сумма
3. , если сумма> x, то указатель (k - int (k / 2)) -.Повторите с шага 1.
4. Повторите с шага 1 до указателя (int (k / 2))> = указатель (k - int (k / 2)).
5. Теперь возьмите [int (k / 2) - 1, int (k / 2), (k - int (k / 2)), (k - int (k / 2) + 1)]указатели и действуйте аналогично Section B .
6. Повторите выше, сдвинув int (k / 2) - 2 вправо, затем сдвинув (k - int (k / 2) + 2) влево.
7. Расширьте шаг 6, пока вы не сдвинете все указатели

КОНЕЦ

// тьфу !!так много написал !!

Answer 3

Если вы можете использовать любые структуры данных, вы можете просто рассматривать это как проблему с рюкзаком и отслеживать, сколько чисел вы использовали в дополнение к сумме.

numbers = [xxx]
buckets = [[0,0] for x in range(MAX_SUM)]
buckets[0][0] = 1;
for number in numbers:
    for bucketi in range(MAX_SUM):
        if buckets[bucketi][0] == 1 and buckets[bucketi][1] < k: 
           buckets[bucketi+number][0] = 1;
           buckets[bucketi+number][1] = buckets[bucketi][1] + 1;

Вот также попытка понять, к чему стремился @Patrick, я не уверен в пределе, но это интересная идея.

def go_(numbers, range_bottom,range_top,sum_target,k,min_v,max_v,nums):
    min_v_,max_v_,res_ = go(numbers, range_bottom,range_top,sum_target-sum(nums),k)
    min_v = min(min_v,min_v_)
    max_v = max(max_v,max_v_)
    if len(res_) > 0:
        newres = [x for x in res_]
        newres = newres+nums
        return [0,0,newres]
    return [min_v,max_v,res_]

def go(numbers, range_bottom,range_top,sum_target,k):

    if sum_target==0 and k == 0:
        return [0,0,['-']];
    elif sum_target<0 or k==0 or range_bottom == range_top:
        return [sum_target,sum_target,[]]


    min_v = 666; max_v = -666;

    if range_top-range_bottom>1:
        min_v ,max_v, res_ = go_(numbers, range_bottom+1, range_top-1, sum_target,k-2,min_v,max_v,[numbers[range_bottom],numbers[range_top-1\
]])
        if len(res_):

            return [0,0,res_];

    if not ( min_v<0 and max_v<0 ):
        min_v ,max_v, res_ = go_(numbers, range_bottom+1, range_top, sum_target ,k,min_v,max_v ,[])
        if len(res_):


            return [0,0,res_];


    if not ( min_v>0 and max_v>0 ):
        min_v ,max_v, res_ = go_(numbers, range_bottom, range_top-1, sum_target,k,min_v,max_v,[])
        if len(res_):

            return [0,0,res_];

    return [min_v,max_v,res_]