algorithm - 内存受限的硬币可更改多达 10 亿的数字

Question

我在一次培训中遇到了这个问题。即我们给了 N 不同的值( N<= 100 )。让我们将这个数组命名为 A[N] ，对于这个数组 A，我们确定数组中有 1 并且 A[i] ≤ 109。 其次，我们给出了数字 S ，其中 S ≤ 109。

现在我们必须用这个值解决经典的硬币问题。实际上，我们需要找到与 S 相加的最小元素数。 A 中的每个元素都可以无限次使用。

时间限制:1 秒

内存限制:256 MB

示例:

S = 1000, N = 10

A[] = {1,12,123,4,5,678,7,8,9,10}. The result is 10.

1000 = 678 + 123 + 123 + 12 + 12 + 12 + 12 + 12 + 12 + 4

我试过的

我试图用经典的动态编程硬币问题技术解决这个问题，但它使用了太多的内存并且超出了内存限制。

我不知道我们应该保留哪些值(value)观。提前致谢。

以下是经典 dp 硬币问题无法解决的几个测试用例。

S = 1000000000 N = 100

1 373241370 973754081 826685384 491500595 765099032 823328348 462385937 
251930295 819055757 641895809 106173894 898709067 513260292 548326059 
741996520 959257789 328409680 411542100 329874568 352458265 609729300 
389721366 313699758 383922849 104342783 224127933 99215674 37629322 
230018005 33875545 767937253 763298440 781853694 420819727 794366283 
178777428 881069368 595934934 321543015 27436140 280556657 851680043 
318369090 364177373 431592761 487380596 428235724 134037293 372264778 
267891476 218390453 550035096 220099490 71718497 860530411 175542466 
548997466 884701071 774620807 118472853 432325205 795739616 266609698 
242622150 433332316 150791955 691702017 803277687 323953978 521256141 
174108096 412366100 813501388 642963957 415051728 740653706 68239387 
982329783 619220557 861659596 303476058 85512863 72420422 645130771 
228736228 367259743 400311288 105258339 628254036 495010223 40223395 
110232856 856929227 25543992 957121494 359385967 533951841 449476607 
134830774
OUTPUT FOR THIS TEST CASE: 5

S = 999865497 N = 7

1 267062069 637323855 219276511 404376890 528753603 199747292
OUTPUT FOR THIS TEST CASE: 1129042

S = 1000000000 N = 40

1 12 123 4 5 678 7 8 9 10 400 25 23 1000 67 98 33 46 79 896 11 112 1223 412 
532 6781 17 18 19 170 1400 925 723 11000 607 983 313 486 739 896
OUTPUT FOR THIS TEST CASE: 90910

Answer 1

(注意:为了清晰起见进行了更新和编辑。最后添加了复杂性分析。)

好的，这是我的解决方案，包括我对@PeterdeRivaz 发现的性能问题的修复。我已经针对问题和评论中提供的所有测试用例对此进行了测试，并且它在一秒钟内完成(好吧，在一个案例中为 1.5 秒)，主要仅使用部分结果缓存的内存(我猜约 16MB)。

我没有使用传统的 DP 解决方案(它既太慢又需要太多内存)，而是使用深度优先、贪婪优先的组合搜索，并使用当前最佳结果进行修剪。我很惊讶(非常)这和它一样有效，但我仍然怀疑您可以构建需要最坏情况指数时间的测试集。

首先有一个主函数，它是调用代码唯一需要调用的东西。它处理所有设置和初始化并调用其他所有内容。 (所有代码都是C#)

// 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's 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;
}

分析:

内存:此算法的内存使用情况很容易确定。基本上只有部分结果缓存和堆栈。缓存固定在 appx。 100 万个条目乘以每个条目的大小(3*4 字节)，所以大约 12MB。堆栈限制为 O(N) ，所以放在一起，内存显然不是问题。

CPU:这个算法的运行时复杂度一开始很难确定，然后变得越来越难，所以请原谅我，因为这里有很多人在挥手。我试图搜索仅对蛮力问题的分析(对 N*kn 基值总和的组合搜索与 S 相加)，但结果并不多。很少有人会说它是 O(N^S) ，这显然太高了。我认为更公平的估计是 O(N^(S/N))或可能 O(N^(S/AVG(N))甚至 O(N^(S/(Gmean(N)))哪里 Gmean(N)是 N[] 元素的几何平均值。该解决方案从蛮力组合搜索开始，然后通过两个重要的优化对其进行改进。

第一个是基于对该分支的最佳可能结果与它已经找到的最佳结果的估计来修剪分支。如果最佳情况估计器完全准确并且分支的工作完全分布，这意味着如果我们发现结果优于其他可能情况的 90%，那么修剪将有效地消除 90% 的工作那一点。长话短说，这应该表明修剪后仍然剩余的工作量应该随着它的进行而和谐地收缩。假设应该应用某种求和/积分来获得工作总数，在我看来，这可以计算为原始工作的对数。所以让我们称之为 O(Log(N^(S/N)) , 或 O(N*Log(S/N))这非常好。 (虽然 O(N*Log(S/Gmean(N))) 可能更准确)。

然而，这有两个明显的漏洞。首先，确实，最佳情况估计量并不完全准确，因此它们不会像上面假设的那样有效地修剪，但是，这在某种程度上被分支的贪婪优先排序所抵消，这提供了最佳机会在搜索的早期找到更好的解决方案，从而提高修剪的效率。

第二个问题是当 N 的不同值相距很远时，最佳情况估计器效果更好。具体来说，如果 |(S/n2 - S/n1)| > 1对于 N 中的任意 2 个值，它几乎变得非常有效。对于小于 SQRT(S) 的 N 值，即使是两个相邻的值 (k, k+1) 也相距足够远，因此该规则适用。然而，对于增加高于 SQRT(S) 的值，会打开一个窗口，因此该窗口内的任意数量的 N 值将无法有效地相互修剪。这个窗口的大小大约是 K/SQRT(S)。因此，如果 S=10^9，当 K 大约为 10^6 时，此窗口的宽度将接近 30 个数字。这意味着 N[] 可以包含 1 加上从 1000001 到 1000029 的每个数字，修剪优化几乎没有任何好处。

为了解决这个问题，我添加了部分结果缓存，它允许内存最近的部分总和到目标 S。这利用了这样一个事实，即当 N 值靠近在一起时，它们往往具有极高的数字总和中的重复项。据我所知，这种有效性大约是问题大小的第 J 个根的 N 倍，其中 J = S/K K 是 N 值平均大小的某种度量(Gmean(N) 可能是最好的估计)。如果我们将此应用于蛮力组合搜索，假设修剪无效，我们得到 O((N^(S/Gmean(N)))^(1/Gmean(N))) ，我认为也是 O(N^(S/(Gmean(N)^2))) .

所以，在这一点上选择你。我知道这真的很粗略，即使它是正确的，它仍然对 N 值的分布非常敏感，因此有很多方差。