Алгоритм интервью

Ответ 1

После некоторого рассмотрения, я считаю, что это NP-полная проблема. Рассмотрим:

A = [0, 0, 0, ..., 0]
B = [b1, b2, b3, ..., bn]

Заметим, что каждая конструкция третьего множества C = ( A[i] or B[i] for i = 0..n ) есть просто объединение некоторого подмножества A и некоторого подмножества B. В этом случае, поскольку каждое подмножество A суммируется с 0, сумма C совпадает с суммой некоторого подмножества B.

Теперь ваш вопрос "Сколько способов построить C с суммой меньше K?" можно пересчитать как "Сколько подмножеств B суммируется меньше чем K?". Решение этой проблемы для K = 1 и K = 0 дает решение проблемы суммирования подмножества для B (разница между этими двумя решениями число подмножеств, сумма которых равна 0).

По аналогичному аргументу даже в общем случае, когда A содержит ненулевые элементы, мы можем построить массив S = [b1-a1, b2-a2, b3-a3, ..., bn-an], и вопрос будет "Сколько подмножеств S суммируется с точностью до K - sum(A)?"

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

Ответ 2

Итак, выбирайте 2 ^ N, так как в каждой точке вы либо выбираете из A, либо из B. В конкретном примере вы указываете, где N - 3, а 8. Для обсуждения вы можете охарактеризовать каждый набор решений как бит.

Так как подход с грубой силой будет пытаться использовать каждый бит.

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

Вы также можете вычислить максимальные суммы, которые могут быть достигнуты от каждого бита до конца таблицы. Если в любой момент ваша общая сумма плюс максимум, который вы можете получить здесь, вниз, меньше, чем K, то каждое поддерево от того, где вы находитесь, является приемлемым без какой-либо необходимости обхода. Случай, как обсуждалось в комментариях, где каждая отдельная комбинация является приемлемой, является частным случаем этого наблюдения.

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

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

В этом случае рекурсивная реализация проще всего, например. (в C)

/* assume A, B and N are known globals */

unsigned int numberOfGoodArraysFromBit(
           unsigned int bit,
           unsigned int runningTotal,
           unsigned int limit)
{
    // have we ended up in an unacceptable subtree?
    if(runningTotal > limit) return 0;

    // have we reached the leaf node without at any
    // point finding this subtree to be unacceptable?
    if(bit >= N) return 1;

    // maybe every subtree is acceptable?
    if(runningTotal + MAXV[bit] <= limit)
    {
        return 1 << (N - bit);
    }

    // maybe no subtrees are acceptable?
    if(runningTotal + MINV[bit] > limit)
    {
        return 0;
    }

    // if we can't prima facie judge the subtreees,
    // we'll need specifically to evaluate them
    return
       numberOfGoodArraysFromBit(bit+1, runningTotal+A[bit], limit) +
       numberOfGoodArraysFromBit(bit+1, runningTotal+B[bit], limit);
}

// work out the minimum and maximum values at each position
for(int i = 0; i < N; i++)
{
    MAXV[i] = MAX(A[i], B[i]);
    MINV[i] = MIN(A[i], B[i]);
}

// hence work out the cumulative totals from right to left
for(int i = N-2; i >= 0; i--)
{
    MAXV[i] += MAXV[i+1];
    MINV[i] += MINV[i+1];
}

// to kick it off
printf("Total valid combinations is %u", numberOfGoodArraysFromBit(0, 0, K));

Я просто думаю об этом; вероятно, существуют лучшие решения.

Ответ 3

"Пожалуйста, напишите алгоритм , чтобы узнать общее число хорошего массивы заданными массивами A, B и числом K."

Разве это не цель?

int A[];
int B[];
int N;
int K;
int Solutions = 0;

void FindSolutons(int Depth, int theSumSoFar) {
    if (theSumSoFar > K) return;
    if (Depth >= N) {
    Solutions++;
    return;
    }

    FindSolutions(Depth+1,theSumSoFar+A[Depth]);
    FindSolutions(Depth+1,theSumSoFar+B[Depth]);
}

Вызвать FindSolutions с обоими аргументами, установленными на ноль. При возврате Solutions будет равно числу хороших массивов;

Ответ 4

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

подумайте о массивах

A=[3,5,9,8,2]
B=[7,5,1,8,2]

если элементы 0..N-1

количество вариантов

2 ^ N

C1=0,C2=0

for all A[i]=B[i] 
{
    C1++
    C2+=A[i]+B[i]
}

затем создайте новые два массива, например

A1=[3,5,9]
B1=[7,5,1]

также теперь C2 составляет 10

теперь число всех вариантов сводится к 2 ^ (N-C1)

теперь вычислить все хорошие числа

с использованием "K" при K = K-C2

к сожалению, независимо от того, какой метод вы используете, у вас есть для вычисления суммы 2 ^ (N-C1) раз