内存受限的硬币找零问题，适用于小于十亿的数字

Question

内存受限的硬币找零问题，适用于小于十亿的数字

algorithmdynamic-programmingcombinatoricsknapsack-problemspace-complexity

24

我在一次培训中遇到了这个问题。我们有N个不同的值（N<= 100）。我们把这个数组称为A[N]，对于这个数组A，我们确定其中有一个1，而且A[i] ≤ 10⁹。其次，我们给出了数字S，其中S ≤ 10⁹。

现在我们需要使用这些值来解决经典的硬币问题。实际上，我们需要找到最少的元素数，使它们的总和恰好为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

我尝试过什么

我尝试使用经典的动态规划硬币问题技术来解决这个问题，但它使用了太多内存并且超过了内存限制。

我无法弄清楚我们应该保留哪些值。提前感谢您的帮助。

这里是几个无法使用经典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

- someone12321

1

“classic dp coin problem technique” 是什么意思？你试过这个吗？https://en.wikipedia.org/wiki/Change-making_problem#Optimal_Substructure - גלעד ברקן

3

请您在这里发布您的代码吗？使用的内存不应该超过S的因子，这不应该成为一个大问题。 - Saeed Amiri

1

@Vidor Vistrom，我已经阅读了你的代码，但是由于没有注释，我很难看出它的作用，而且我也不确定为什么要在int和Integer之间切换。也许你应该写一个详细的解释？ - templatetypedef

1

我添加了三个最难解决的测试用例。 - someone12321

1

你能在1秒内使用DP解决吗？ - Pushan Gupta

显示剩余25条评论

2个回答

3

[我已经放弃了之前的位运算想法，因为它看起来太耗时了]

这是一个有点疯狂但不完整的想法，但可能有效。

让我们从介绍f(n,s)开始，它返回从n枚硬币中组成s的组合数量。

现在，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枚硬币可能得到哪些数，而不需要递增地进行计算，只需计算F(a)的n次幂并应用反向傅里叶变换。

这使我们能够进行一种二分搜索，帮助处理答案很大的情况。

正如我所说，这个想法不完整 - 目前我不知道如何将位表示与傅里叶变换结合起来（以满足内存约束），并且我们是否能在任何“普通”CPU的1秒内完成计算...

- maxim1000

如何从我们可以制作的总和列表转换为制作总和所需的最少硬币数量？ - templatetypedef

硬币的数量只是我们迭代的索引 - 一旦我们发现该数字集合包含所需的数字，我们就输出迭代的索引。 - maxim1000

我认为你可能有所发现，但是关于f(n,s)和a(i)的含义存在着太多不明确和术语转换。如果它们应该是递归定义的序列或函数，那么您需要至少描述它们的基础或终止情况。 - RBarryYoung

@RBarryYoung，它们只是函数（或数组），但也许将f(n,s)称为fn(s)会更好，这样就清楚了我们计算傅里叶变换的数组。 - maxim1000

问题不在于数组与函数等的比较。问题在于您没有定义它们的内容/返回值得足够清晰，以至于我们无法弄清它们应该代表/包含什么。 - RBarryYoung

显示剩余3条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- RBarryYoung · Accepted Answer

(注意：为了更加清晰，已进行更新和编辑。复杂度分析位于最后。)

好的，这是我的解决方案，包括我对@PeterdeRivaz 发现的性能问题所做的修复。我已经测试了所有在问题和评论中提供的测试用例，它们都可以在不到1秒（在某些情况下是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;
}

分析:

内存：

这个算法的内存使用很容易确定。基本上只有部分结果缓存和堆栈。缓存固定为大约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%的工作量。长话短说，在这里，我认为还应该应用一些求和/积分来得出总工作量，这对我来说似乎是对原始工作的对数级别。因此，让我们称之为O(Log(N^(S/N))，或者O(N*Log(S/N))，这非常好。（尽管O(N*Log(S/Gmean(N)))可能更准确）。

然而，这有两个明显的漏洞。首先，最优情况的估算器不完全准确，因此他们不会像上面所假设的那样有效地修剪，但是，这在某种程度上被贪心-优先排序分支所平衡，这会使搜索早期找到更好的解决方案的机会增加，从而增加修剪的效果。

第二个问题是最佳情况估算器在N的不同值之间相差很远时效果更好。具体来说，如果对于任何两个N中的值，|(S/n2 - S/n1)| > 1，那么它几乎可以完美地起作用。对于小于SQRT(S)的N值，即使是相邻的两个值（k，k+1）也足够远，以至于该规则适用。然而，对于大于SQRT(S)的增加值，会出现一个窗口，使得该窗口内的任意数量的N值都无法有效地互相修剪。这个窗口的大小约为K/SQRT(S)。因此，如果S=10^9，当K约为10^6时，这个窗口将几乎有30个数字宽。这意味着N[]可能包含从1000001到1000029的每个数字加1，修剪优化几乎没有任何效益。

为了解决这个问题，我添加了部分结果缓存，可以记忆最近的部分和达到目标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值的分布非常敏感，所以方差很大。