最近我被问到以下面试问题:你有两组相同长度的数字N,例如A = [3,5,9]和B = [7,5,1].接下来,对于范围0..N-1中的每个位置i,您可以选择数字A [i]或B [i],因此最后您将得到另一个长度为N的数组C,其中包含来自A和A的元素B.如果C中所有元素的总和小于或等于K,那么这样的数组是好的.请编写一个算法,通过给定的数组A,B和数字K来计算出良好数组的总数.
我提出的唯一解决方案是动态编程方法,当我们有一个大小为NxK的矩阵时,M [i] [j]表示如果当前总和等于j,我们可以为数字X [i]组合多少组合.但看起来他们希望我想出一个公式.你能帮帮我吗？至少我应该寻找什么方向？将不胜感激任何帮助.谢谢.
经过一番考虑后,我认为这是一个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完全的,所以这个问题也必须如此.因此,考虑到这一点,我敢说你提出的动态编程解决方案是你能做的最好的,当然也没有神奇的公式存在.