关于面试的算法
最近我被问到以下面试问题:你有两组长度相同的数字N，例如A= 3，5，9和B = 7，5，1。接下来，对于范围0..N-1中的每个位置i，你可以选择数字Ai或Bi，因此在最后你将有另一个长度为N的数组C，它由来自A和B的元素组成。如果C中所有元素的总和小于或等于K，则这种数组是好的。请写一个算法，通过给定的数组A，B和数量K来计算出好的数组的总数。
我想出的唯一解决方案是动态规划方法，当我们有一个大小为NxK的矩阵时，Mi表示如果当前和等于j，我们可以对数字Xi有多少个组合，但看起来他们希望我能想出一个公式。你能帮我一下吗？至少我应该寻找什么方向？都会感谢任何帮助。谢谢。
回答 4
Stack Overflow用户
发布于 2012-10-03 09:28:43
经过一些考虑，我认为这是一个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的某个子集的和。
现在你的问题是“我们可以用多少种方法用小于K的和来构造C？”可以重述为“B的多少个子集和小于K?”。为K = 1和K = 0解决此问题将产生B的subset sum problem的解决方案(这两个解决方案之间的差异是总和为0的子集的数量)。
通过类似的论证，即使在A包含非零元素的一般情况下，我们也可以构造一个数组S = [b1-a1, b2-a2, b3-a3, ..., bn-an]，问题就变成了“S的多少个子集之和小于K - sum(A)?”
由于子集和问题是NP-完全的，所以这个问题一定也是NP-完全的。因此，考虑到这一点，我敢说您提出的动态编程解决方案是您所能做的最好的解决方案，当然也不存在什么神奇的公式。
Stack Overflow用户
发布于 2012-10-03 08:54:45
所以有2^N个选择，因为在每个点上，你要么从A中选择，要么从B中选择。在你给出的具体例子中，N恰好是3，这里有8。为了讨论，你可以将每组决策描述为一个位模式。
因此，暴力方法将尝试每一个单独的比特模式。
但显而易见的是，如果前几个比特产生的数字太大，那么随后的每一组可能的尾比特也会产生一个太大的数字。因此，更好的建模方式可能是一棵树，在树上，你不需要费心沿着已经生长到超出你极限的四肢行走。
您还可以计算从每一位到表末尾可以达到的最大总和。如果在任何时候，你的运行总数加上你可以从这里获得的最大值小于K，那么你所在的每个子树都是可以接受的，不需要任何遍历。正如评论中所讨论的，每一种组合都是可接受的情况是这种观察的特例。
正如Serge在下面指出的，一个相关的观察是我们最小化，并使用反向逻辑来取消整个子树，而不是遍历。
一个潜在的进一步优化背后的观察是，只要我们以相同的方式洗牌，改变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));我只是即兴思考；可能存在更好的解决方案。
Stack Overflow用户
发布于 2012-10-03 08:55:11
“请写一个算法，根据给定的数组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将等于良好数组的数量；
https://stackoverflow.com/questions/12700378
复制相似问题
腾讯云开发者
