受内存限制的硬币更换数量高达十亿 [英] Memory-constrained coin changing for numbers up to one billion
问题描述
我在一次培训中就遇到了这个问题。也就是说，我们给了 N 个不同的值（ N <= 100 ）。我们将此数组命名为 A [N] ，对于此数组A，我们确定数组中有1，而 A [i] ≤ 10 9 。其次，给定数字 S 其中 S ≤ 10 9 。
现在我们必须用该值解决经典硬币问题。实际上，我们需要找到最小数量的元素，这些元素的总和将恰好等于 S 。 A 中的每个元素都可以使用无数次。
-
时间限制：1秒
-
内存限制：256 MB
示例：
S = 1000，N = 10
A [] = {1,12,123,4,5,678,7,8,9,10}。结果为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 411542100 329874568 352458265 609729300
389721366 313699758 383922849 104342783 224127933 99215674 37629322
230018005 33875545 767937253 763298440 781853694 420819727 794366283
178777428 881069368 369b 280b 680b 280280 523b 367450 374b 367450 374b 367230 374b 368b 367b 367b 367b 367b 367b 1280b 367280 374280 374b 370b 1280b 367834 374280 374280 523680b 367b 368b 367b 367374a 523680b 367760a 374280 367b 367654 374b 367856 374280 523680b 374654 374 bs 23574357巧笔$ b 267891476 218390453 550035096 220099490 71718497 860530411 175542466
548997466 884701071 774620807 118472853 432325205 795739616 266609698
242622150 433332316 150791955 691702017 803277687 323953978 521256957 513b 521963957 6 68239387
982329783 619220557 861659596 303476058 85512863 72420422 645130771
228736228 367259743 400311288 105258339 628254036 495010223 40223395
110232856 856929227 25543992 957121494 359385967 533951841 EST 476b $ b 5
S = 999865497 N = 7
1 267062069 637323855 219276511 404376890 528753603 199747292
此测试案例的输出：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
此测试案例的输出：90910
（注意：为清楚起见，已对其进行更新和编辑。最后，添加了复杂性分析。）
好的，这是我的解决方案，包括对@PeterdeRivaz发现的性能问题的修复。我已经针对问题和注释中提供的所有测试用例进行了测试，并且在一秒钟之内完成了所有操作（一次，1.5s），主要只使用了部分结果缓存的内存（我猜是大约16MB）。
而不是使用传统的DP解决方案（速度太慢且需要太多内存），我使用了深度优先，贪婪优先的组合使用当前最佳结果进行修剪搜索。我对此感到惊讶（非常），而且效果很好，但是我仍然怀疑您可以构建测试集，而这将花费最坏情况下的指数时间。
<首先，有一个主函数是调用代码唯一需要调用的东西。它处理所有的设置和初始化，并调用其他所有内容。 （所有代码均为C＃）
//查找指定金额的硬币的最小数量
int CountChange（int targetSum，int []个硬币）
{
//初始化（部分）记忆的缓存
PrevResultCache = new PartialResult [1048576];
//确保硬币从最低到最高
排序Array.Sort（coins）;
int curBest = targetSum;
int结果= CountChange_r（targetSum，coins，coins.GetLength（0）-1，0，ref curBest）;
返回结果；
}
由于@PeterdeRivaz提出的问题测试用例，我还添加了一个当N []中有大量靠近在一起时，将处理部分结果缓存。
以下是缓存的代码：
//为以前的剩余计数结果实现一个非常简单的缓存
struct PartialResult
{
public int PartialSum;
public int CoinVal;
public int RemainingCount;
}
PartialResult [] PrevResultCache;
//检查部分计数缓存中已计算的结果
int PrevAddlCount（int currSum，int currCoinVal）
{
int cacheAddr = currSum& 1048575; //和（2 ^ 20-1）进行运算，仅获得前20位
PartialResult prev = PrevResultCache [cacheAddr];
//使用它，只要它实际上是相同的部分总和
// //硬币值至少等于当前硬币
if（（prev。 PartialSum == currSum）&&（prev.CoinVal> = currCoinVal））
{
return prev.RemainingCount;
}
//否则标记为空
返回0;
}
//将新值添加或覆盖到缓存
void AddPartialCount（int currSum，int currCoinVal，int fullyCount）
{
int cacheAddr = currSum& 1048575; //和（2 ^ 20-1）进行运算，仅获得前20位
PartialResult prev = PrevResultCache [cacheAddr];
//仅在总和不同或结果更好时才添加
if（（prev.PartialSum！= currSum）
||（prev.CoinVal< = currCoinVal ）
||（prev.RemainingCount == 0）
||（prev.RemainingCount> =剩余计数）
）
{
prev.PartialSum = currSum;
prev.CoinVal = currCoinVal;
prev.RemainingCount =剩余计数;
PrevResultCache [cacheAddr] = prev;
}
}
这是递归函数的代码实际计数：
/ *
*查找总特定金额$ b $所需的最小硬币数量b *使用通过的硬币面额清单。
*
*内存要求：O（N），其中N是硬币面额的数量
*（主要用于堆叠）
*
* CPU要求：O （Sqrt（S）* N），其中S是目标总和
*（平均，估计。很难弄清楚。）
* /
int CountChange_r（int targetSum，int []硬币，int coinIdx，int curCount，ref int curBest）
{
int coinVal = coins [coinIdx];
int newCount = 0;
//检查我们是否在搜索树的末尾（curIdx = 0，coinVal = 1）
// //是否达到了目标总和
if（ （coinVal == 1）||（targetSum == 0））
{
//仅使用数学运算获得该路径/组合的最终总数
newCount = curCount + targetSum;
//更新，如果我们有新的curBest
if（newCount
}
//如果无法改善当前分支，则修剪整个分支。Best
int bestPossible = curCount +（targetSum / coinVal）;
if（bestPossible> = curBest）
return bestPossible; //注意：这是一个错误的答案，但这与
无关紧要，因为我们永远不要使用它。
//检查缓存，以查看是否存在该部分金额
//的剩余计数（并且使用的硬币至少与我们的硬币一样大）
int prevRemCount = PrevAddlCount（targetSum，coinVal）;
if（prevRemCount> 0）
{
//它存在，因此使用它
newCount = prevRemCount + targetSum;
//更新，如果我们有新的curBest
if（newCount
}
//始终首先尝试剩余的最大硬币，从
// //硬币的最大可能数目开始（贪婪优先搜索）
newCount = curCount + targetSum;
for（int cnt = targetSum / coinVal; cnt> = 0; cnt--）
{
int tmpCount = CountChange_r（targetSum-（cnt * coinVal），硬币，coinIdx-1 ，curCount + cnt，ref curBest）;
如果（tmpCount< newCount）newCount = tmpCount;
}
//将新的部分结果添加到缓存
AddPartialCount（targetSum，coinVal，newCount-curCount）;
返回newCount;
}
分析：
内存：
对于此算法，很容易确定内存使用情况。基本上只有部分结果缓存和堆栈。缓存固定为appx。 1百万个条目乘以每个条目的大小（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个值，则几乎完全有效；对于N小于SQRT（S）的值，则即使两个相邻的值（k，k + 1）也足够远该规则适用。但是，要增加值，a在SQRT（S）上打开一个窗口，以使该窗口中的任意数量的N值都无法有效地修剪。该窗口的大小约为K / SQRT（S）。因此，如果S = 10 ^ 9，则当K大约为10 ^ 6时，此窗口将接近30个数字。这意味着N []可能包含1000001到1000029之间的每个数字加上1，并且修剪优化几乎不会带来任何好处。
为解决这个问题，我添加了部分结果高速缓存，它可以记忆到目标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值的分布仍然非常敏感，所以变化很大。
I faced this problem on one training. Namely we have given N different values (N<= 100). Let's name this array A[N], for this array A we are sure that we have 1 in the array and A[i] ≤ 109. Secondly we have given number S where S ≤ 109.
Now we have to solve classic coin problem with this values. Actually we need to find minimum number of element which will sum to exactly S. Every element from A can be used infinite number of times.
Time limit: 1 sec
Memory limit: 256 MB
Example:
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
What I have tried
I tried to solve this with classic dynamic programming coin problem technique but it uses too much memory and it gives memory limit exceeded.
I can't figure out what should we keep about those values. Thanks in advance.
Here are the couple test cases that cannot be solved with the classic dp coin problem.
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
(NOTE: Updated and edited for clarity. Complexity Analysis added at the end.)
OK, here is my solution, including my fixes to the performance issues found by @PeterdeRivaz. I have tested this against all of the test cases provided in the question and the comments and it finishes all in under a second (well, 1.5s in one case), using primarily only the memory for the partial results cache (I'd guess about 16MB).
Rather than using the traditional DP solution (which is both too slow and requires too much memory), I use a Depth-First, Greedy-First combinatorial search with pruning using current best results. I was surprised (very) that this works as well as it does, but I still suspect that you could construct test sets that would take a worst-case exponential amount of time.
First there is a master function that is the only thing that calling code needs to call. It handles all of the setup and initialization and calls everything else. (all code is 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;
}
Because of the problem test-cases raised by @PeterdeRivaz I have also added a partial results cache to handle when there are large numbers in N[] that are close together.
Here is the code for the cache:
// 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;
}
}
And here is the code for the recursive function that does the actual counting:
/*
* 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;
}
Analysis:
Memory:
Memory usage is pretty easy to determine for this algorithm. Basiclly there's only the partial results cache and the stack. The cache is fixed at appx. 1 million entries times the size of each entry (3*4 bytes), so about 12MB. The stack is limited toO(N), so together, memory is clearly not a problem.
CPU:
The run-time complexity of this algorithm starts out hard to determine and then gets harder, so please excuse me because there's a lot of hand-waving here. I tried to search for an analysis of just the brute-force problem (combinatorial search of sums of N*kn base values summing to S) but not much turned up. What little there was tended to say it wasO(N^S), which is clearly too high. I think that a fairer estimate is O(N^(S/N)) or possibly O(N^(S/AVG(N)) or even O(N^(S/(Gmean(N))) where Gmean(N) is the geometric mean of the elements of N[]. This solution starts out with the brute-force combinatorial search and then improves it with two significant optimizations.
The first is the pruning of branches based on estimates of the best possible results for that branch versus what the best result it has already found. If the best-case estimators were perfectly accurate and the work for branches was perfectly distributed, this would mean that if we find a result that is better than 90% of the other possible cases, then pruning would effectively eliminate 90% of the work from that point on. To make a long story short here, this should work out that the amount of work still remaining after pruning should shrink harmonically as it progress. Assuming that some kind of summing/integration should be applied to get a work total, this appears to me to work out to a logarithm of the original work. So let's call it O(Log(N^(S/N)), or O(N*Log(S/N)) which is pretty darn good. (Though O(N*Log(S/Gmean(N))) is probably more accurate).
However, there are two obvious holes with this. First, it is true that the best-case estimators are not perfectly accurate and thus they will not prune as effectively as assumed above, but, this is somewhat counter-balanced by the Greedy-First ordering of the branches which gives the best chances for finding better solutions early in the search which increase the effectiveness of pruning.
The second problem is that the best-case estimator works better when the different values of N are far apart. Specifically, if |(S/n2 - S/n1)| > 1 for any 2 values in N, then it becomes almost perfectly effective. For values of N less than SQRT(S), then even two adjacent values (k, k+1) are far enough apart that that this rule applies. However for increasing values above SQRT(S) a window opens up so that any number of N-values within that window will not be able to effectively prune each other. The size of this window is approximately K/SQRT(S). So if S=10^9, when K is around 10^6 this window will be almost 30 numbers wide. This means that N[] could contain 1 plus every number from 1000001 to 1000029 and the pruning optimization would provide almost no benefit.
To address this, I added the partial results cache which allows memoization of the most recent partial sums up to the target S. This takes advantage of the fact that when the N-values are close together, they will tend to have an extremely high number of duplicates in their sums. As best as I can figure, this effectiveness is approximately the N times the J-th root of the problem size where J = S/K and K is some measure of the average size of the N-values (Gmean(N) is probably the best estimate). If we apply this to the brute-force combinatorial search, assuming that pruning is ineffective, we get O((N^(S/Gmean(N)))^(1/Gmean(N))), which I think is also O(N^(S/(Gmean(N)^2))).
So, at this point take your pick. I know this is really sketchy, and even if it is correct, it is still very sensitive to the distribution of the N-values, so lots of variance.
这篇关于受内存限制的硬币更换数量高达十亿的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
