Ответ 1

(ПРИМЕЧАНИЕ: Обновлено и отредактировано для ясности. Анализ сложности добавлен в конце.)

ОК, вот мое решение, включая мои исправления проблем производительности, обнаруженных @PeterdeRivaz. Я проверил это на все тестовые примеры, предоставленные в вопросе и комментариях, и он заканчивает все в течение секунды (ну, 1,5 с в одном случае), используя в основном только память для кеша частичных результатов (я бы догадался около 16 МБ).

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

Сначала есть главная функция, которая является единственной вещью, которую должен вызвать вызывающий код. Он обрабатывает все настройки и инициализацию и вызывает все остальное. (весь код С#)

// Find the min# of coins for a specified sum
int CountChange(int targetSum, int[] coins)
{
    // init the cache for (partial) memoization
    PrevResultCache = new PartialResult[1048576];

    // make sure the coins are sorted lowest to highest
    Array.Sort(coins);

    int curBest = targetSum;
    int result = CountChange_r(targetSum, coins, coins.GetLength(0)-1, 0, ref curBest);

    return result;
}

Из-за проблемных тестовых случаев, вызванных @PeterdeRivaz, я также добавил кэш частичных результатов для обработки, когда большие числа в N [] находятся близко друг к другу.

Вот код для кеша:

    // implement a very simple cache for previous results of remainder counts
    struct PartialResult
    {
        public int PartialSum;
        public int CoinVal;
        public int RemainingCount;
    }
    PartialResult[] PrevResultCache;

    // checks the partial count cache for already calculated results
    int PrevAddlCount(int currSum, int currCoinVal)
    {
        int cacheAddr = currSum & 1048575;  // AND with (2^20-1) to get only the first 20 bits
        PartialResult prev = PrevResultCache[cacheAddr];

        // use it, as long as it actually the same partial sum 
        // and the coin value is at least as large as the current coin
        if ((prev.PartialSum == currSum) && (prev.CoinVal >= currCoinVal))
        {
            return prev.RemainingCount;
        }
        // otherwise flag as empty
        return 0;
    }

    // add or overwrite a new value to the cache
    void AddPartialCount(int currSum, int currCoinVal, int remainingCount)
    {
        int cacheAddr = currSum & 1048575;  // AND with (2^20-1) to get only the first 20 bits
        PartialResult prev = PrevResultCache[cacheAddr];

        // only add if the Sum is different or the result is better
        if ((prev.PartialSum != currSum)
            || (prev.CoinVal <= currCoinVal)
            || (prev.RemainingCount == 0)
            || (prev.RemainingCount >= remainingCount)
            )
        {
            prev.PartialSum = currSum;
            prev.CoinVal = currCoinVal;
            prev.RemainingCount = remainingCount;
            PrevResultCache[cacheAddr] = prev;
        }
    }

И вот код для рекурсивной функции, который выполняет фактический подсчет:

/*
* Find the minimum number of coins required totaling to a specifuc sum
* using a list of coin denominations passed.
*
* Memory Requirements: O(N)  where N is the number of coin denominations
*                            (primarily for the stack)
* 
* CPU requirements:  O(Sqrt(S)*N) where S is the target Sum
*                           (Average, estimated.  This is very hard to figure out.)
*/
int CountChange_r(int targetSum, int[] coins, int coinIdx, int curCount, ref int curBest)
{
    int coinVal = coins[coinIdx];
    int newCount = 0;

    // check to see if we are at the end of the search tree (curIdx=0, coinVal=1)
    // or we have reached the targetSum
    if ((coinVal == 1) || (targetSum == 0))
    {
        // just use math get the final total for this path/combination 
        newCount = curCount + targetSum;
        // update, if we have a new curBest
        if (newCount < curBest) curBest = newCount;
        return newCount;
    }

    // prune this whole branch, if it cannot possibly improve the curBest
    int bestPossible = curCount + (targetSum / coinVal);
    if (bestPossible >= curBest) 
            return bestPossible; //NOTE: this is a false answer, but it shouldnt matter
                                    //  because we should never use it.

    // check the cache to see if a remainder-count for this partial sum
    // already exists (and used coins at least as large as ours)
    int prevRemCount = PrevAddlCount(targetSum, coinVal);
    if (prevRemCount > 0)
    {
        // it exists, so use it
        newCount = prevRemCount + targetSum;
        // update, if we have a new curBest
        if (newCount < curBest) curBest = newCount;
        return newCount;
    }

    // always try the largest remaining coin first, starting with the 
    // maximum possible number of that coin (greedy-first searching)
    newCount = curCount + targetSum;
    for (int cnt = targetSum / coinVal; cnt >= 0; cnt--)
    {
        int tmpCount = CountChange_r(targetSum - (cnt * coinVal), coins, coinIdx - 1, curCount + cnt, ref curBest);

        if (tmpCount < newCount) newCount = tmpCount;
    }

    // Add our new partial result to the cache
    AddPartialCount(targetSum, coinVal, newCount - curCount);

    return newCount;
}

Анализ:

Память:

CPU:

Во-первых, это обрезка ветвей, основанная на оценках наилучших результатов для этой ветки по сравнению с тем, что лучший результат, который он уже нашел. Если бы оценки наилучшего случая были совершенно точными и работа над веткими была прекрасно распределена, это означало бы, что, если мы найдем результат, который лучше 90% других возможных случаев, тогда обрезка эффективно устранит 90% работы из это пункт сверху. Короче говоря, это должно решить, что объем работы, оставшейся после обрезки, должен гармонично сокращаться по мере ее продвижения. Предполагая, что какое-то суммирование/интеграция следует применять для получения общей работы, мне представляется, что она работает с логарифмом оригинальной работы. Поэтому позвольте называть его O(Log(N^(S/N)) или O(N*Log(S/N)), что довольно хорошо. (Хотя O(N*Log(S/Gmean(N))), вероятно, более точна).

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

Вторая проблема заключается в том, что лучшая оценка лучше работает, когда разные значения N находятся далеко друг от друга. В частности, если |(S/n2 - S/n1)| > 1 для любых 2 значений в N, то оно становится почти идеально эффективным. Для значений N меньше, чем SQRT (S), то даже два смежных значения (k, k + 1) достаточно далеко друг от друга, что это правило применяется. Однако для увеличения значений выше SQRT (S) открывается окно, так что любое количество N-значений внутри этого окна не сможет эффективно обрезать друг друга. Размер этого окна составляет приблизительно K/SQRT (S). Поэтому, если S = ​​10 ^ 9, когда K составляет около 10 ^ 6, это окно будет шириной почти 30. Это означает, что N [] может содержать 1 плюс каждое число от 1000001 до 1000029, а оптимизация обрезки практически не принесет пользы.

Чтобы решить эту проблему, я добавил кэш частичных результатов, который позволяет запоминать последние частичные суммы до целевого S. Это использует тот факт, что когда значения N близки друг к другу, они будут иметь тенденцию иметь чрезвычайно большое количество дубликатов в их суммах. Насколько я могу судить, эта эффективность примерно равна N разму J -му корню размера проблемы, где J = S/K и K - некоторая мера среднего размера N-значений (Gmean (N), вероятно, лучший оценить). Если мы применим это к комбинаторному поиску грубой силы, считая, что обрезка неэффективна, мы получаем O((N^(S/Gmean(N)))^(1/Gmean(N))), что, я думаю, также O(N^(S/(Gmean(N)^2))).

Итак, в этот момент возьмите свой выбор. Я знаю, что это действительно отрывочно, и даже если это правильно, оно по-прежнему очень чувствительно к распределению N-значений, поэтому много дисперсии.

Ответ 2

[Я заменил предыдущую идею о битовых операциях, потому что кажется, что это слишком много времени]

Немного сумасшедшая идея и неполная, но может работать.

Начнем с введения f(n,s), который возвращает число комбинаций, в которых s может быть составлено из n монет.

Теперь, как f(n+1,s) связано с f(n)?

Один из возможных способов его расчета:

f(n+1,s)=sum[coin:coins]f(n,s-coin)

Например, если у нас есть монеты 1 и 3,

f(0,)=[1,0,0,0,0,0,0,0] - с нулевыми монетами мы можем иметь только нулевую сумму

f(1,)=[0,1,0,1,0,0,0,0] - то, что мы можем иметь с одной монетой

f(2,)=[0,0,1,0,2,0,1,0] - то, что мы можем иметь с двумя монетами

Мы можем переписать его несколько иначе:

f(n+1,s)=sum[i=0..max]f(n,s-i)*a(i)

a(i)=1 если у нас есть монета i и 0 в противном случае

Мы имеем здесь свертку: f(n+1,)=conv(f(n,),a)

https://en.wikipedia.org/wiki/Convolution

Вычисляя это как определение, дает O(n^2)

Но мы можем использовать преобразование Фурье, чтобы свести его к O (n * log n).

https://en.wikipedia.org/wiki/Convolution#Convolution_theorem

Итак, теперь у нас есть более или менее дешевый способ узнать, какие числа возможны с монетами n, не увеличиваясь - просто вычислите n-th мощность F(a) и примените обратное преобразование Фурье.

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

Как я уже сказал, идея неполная - на данный момент я понятия не имею, как комбинировать представление битов с преобразованиями Фурье (чтобы удовлетворить ограничение памяти), и будем ли мы вписываться в 1 секунду на любом "регулярном" процессоре...