10

最近有人问我以下面试问题：你有两组相同长度的数字N，例如A = [3, 5, 9]和B = [7, 5, 1]。接下来，对于范围 0..N-1 中的每个位置 i，您可以选择数字 A[i] 或 B[i]，因此最后您将拥有另一个长度为 N 的数组 C，其中包含来自 A 和B.如果C中所有元素的总和小于或等于K，那么这样的数组是好的。请编写一个算法，通过给定的数组 A、B 和数字 K 来计算好的数组的总数。

我提出的唯一解决方案是动态编程方法，当我们有一个大小为 NxK 的矩阵时，M[i][j] 表示如果当前总和等于 j，我们可以对数字 X[i] 有多少组合。但看起来他们希望我想出一个公式。你能帮我解决这个问题吗？至少我应该寻找什么方向？将不胜感激任何帮助。谢谢。

4

4 回答 4

9

经过一番考虑，我相信这是一个 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。

现在你的问题是“我们可以用多少种方法构建C一个总和小于K？” 可以重述为“B总和的多少子集小于K？”。解决这个问题K = 1并K = 0产生子集和问题的解决方案B（两个解决方案之间的差异是总和为 0 的子集的数量）。

通过类似的论点，即使在包含非零元素的一般情况下A，我们也可以构造一个数组S = [b1-a1, b2-a2, b3-a3, ..., bn-an]，问题变成“和有多少个子集S小于K - sum(A)？”

由于子集和问题是NP完全的，所以这个问题也一定是。因此，考虑到这一点，我敢说你提出的动态编程解决方案是你能做的最好的，当然不存在神奇的公式。

于 2012-10-03T01:28:43.247 回答
0

所以有 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));

我只是即兴思考；可能存在更好的解决方案。

于 2012-10-03T00:54:45.273 回答
0

“请编写一个算法，通过给定的数组 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将等于好数组的数量；

于 2012-10-03T00:55:11.370 回答
0

这就是我尝试解决问题的方法（对不起，如果它很愚蠢）

想想数组

A=[3,5,9,8,2]
B=[7,5,1,8,2]

如果元素 0..N-1

选择数量

2^N

C1=0,C2=0

for all A[i]=B[i] 
{
    C1++
    C2+=A[i]+B[i]
}

然后创建新的两个数组，如

A1=[3,5,9]
B1=[7,5,1]

现在C2也是10

现在所有选择的数量减少到 2^(N-C1)

现在计算所有好的数字

使用“K”作为 K=K-C2

不幸的是，无论您使用哪种方法，您都必须计算总和 2^(N-C1) 次

于 2012-10-03T01:13:15.320 回答