动态规划:产品总和

Question

假设您有两个相同长度的列表,L1和L2,N.我们将prodSum定义为:

def prodSum(L1, L2) :
    ans = 0
    for elem1, elem2 in zip(L1, L2) :
        ans += elem1 * elem2

    return ans

是否存在一种有效的算法,假设L1被排序,L2的排列数使得prodSum(L1,L2)<某些预先指定的值？

如果它可以简化问题,你可以假设L1和L2都是来自[1,2,...,N]的整数列表.

编辑:Managu的回答让我确信,如果不假设L1和L2是来自[1,2,...,N]的整数列表,这是不可能的.我仍然对采用这种约束的解决方案感兴趣.

Answer 1

我想首先消除对数学的一定程度的混淆,然后讨论两个解决方案并为其中一个提供代码.

有一个名为#P的计数类,它很像是 - 没有类NP.从定性的角度来说,它比NP更难.没有特别的理由相信这个计数问题比#P-hard更好,尽管证明这一点可能很难或很容易.

然而,许多#P-hard问题和NP难问题在实践中需要花费多长时间才能解决,甚至一个特定的难题也可能更难或更容易,具体取决于输入的属性.NP-hard或#P-hard意味着存在困难的案例.一些NP难题和#P难题也有较少的难题甚至是直接容易的案例.(其他人的案例似乎比最难的案件容易得多.)

因此,实际问题可能在很大程度上取决于感兴趣的输入.假设阈值位于高端或低端,或者您有足够的内存来获得相当数量的缓存结果.然后有一个有用的递归算法,它使用了两个想法,其中一个已经提到过:(1)在部分分配了一些值之后,列表片段的剩余阈值可以排除所有的排列,或者它可以允许所有的排列他们 (2)内存允许,你应该缓存一些剩余的阈值和一些列表片段的小计.要改进缓存,您可以按顺序从其中一个列表中选择元素.

这是一个实现此算法的Python代码:

list1 = [1,2,3,4,5,6,7,8,9,10,11]
list2 = [1,2,3,4,5,6,7,8,9,10,11]
size = len(list1)
threshold = 396     # This is smack in the middle, a hard value

cachecutoff = 6     # Cache results when up to this many are assigned

def dotproduct(v,w):
    return sum([a*b for a,b in zip(v,w)])

factorial = [1]
for n in xrange(1,len(list1)+1):
    factorial.append(factorial[-1]*n)

cache = {}

# Assumes two sorted lists of the same length

def countprods(list1,list2,threshold):
    if dotproduct(list1,list2) <= threshold:            # They all work
        return factorial[len(list1)]
    if dotproduct(list1,reversed(list2)) > threshold:   # None work
        return 0
    if (tuple(list2),threshold) in cache:               # Already been here
        return cache[(tuple(list2),threshold)]
    total = 0
    # Match the first element of list1 to each item in list2
    for n in xrange(len(list2)):
        total += countprods(list1[1:],list2[:n] + list2[n+1:],
            threshold-list1[0]*list2[n])
    if len(list1) >= size-cachecutoff:
        cache[(tuple(list2),threshold)] = total
    return total

print 'Total permutations below threshold:',
print countprods(list1,list2,threshold)
print 'Cache size:',len(cache)

正如评论专栏所说,我测试了这个代码的硬阈值.它比所有排列的天真搜索快得多.

如果满足三个条件,还有另一种算法优于此算法:(1)没有足够的内存用于良好的缓存,(2)列表条目是小的非负整数,(3)你'对最难的门槛感兴趣.使用第二种算法的第二种情况是,如果您希望所有阈值的计数变平,无论是否满足其他条件.要将此算法用于两个长度为n的列表,首先选择一个基数x,它是10或2的幂,大于n阶乘.现在制作矩阵

M[i][j] = x**(list1[i]*list2[j])

如果使用Ryser公式计算此矩阵M 的永久值,则基数x中的永久物的第k个数字将告诉您点积正好为k的排列数.此外,Ryser公式比直接对所有排列求和要快得多.(但它仍然是指数级的,所以它与计算永久物是#P-hard的事实并不矛盾.)

此外,是的,这组排列是对称组.如果你能以某种方式使用群论来加速这个计数问题,那就太好了.但据我所知,这个问题的描述中没有任何深刻的东西.

最后,如果不是精确计算低于阈值的排列数,而只想近似该数字,那么游戏可能会完全改变.(你可以在多项式时间内逼近永久物,但这在这里没有用.)我必须考虑做什么; 无论如何,这不是提出的问题.

我意识到上面的讨论和上面的代码中缺少另一种缓存/动态编程.代码中实现的缓存是早期缓存:如果只将list1的前几个值分配给list2,并且如果剩余阈值多次出现,则缓存允许代码重用结果.如果list1和list2的条目是不太大的整数,则此方法很有用.但如果条目是典型的浮点数,它将是一个失败的缓存.

但是,当分配了list1的大部分值时,您也可以在另一端预先计算.在这种情况下,您可以为所有剩余值创建小计的排序列表.请记住,您可以按顺序使用list1,并在list2端执行所有排列.例如,假设list1的最后三个条目是[4,5,6],并且假设list2中的三个值(中间的某个位置)是[2.1,3.5,3.7].然后,您将缓存六个点产品的排序列表:

endcache[ [2.1, 3.5, 3.7] ] = [44.9, 45.1, 46.3, 46.7, 47.9, 48.1]

这对你有什么用？如果你查看我发布的代码,函数countprods(list1,list2,threshold)以递归方式使用子阈值.第一个参数list1可能更好地作为全局变量而不是作为参数.如果list2足够短,那么countprods可以通过在listcache [list2]列表中进行二进制搜索来更快地完成工作.(我刚刚从stackoverflow中了解到这是在Python的bisect模块中实现的,尽管性能代码无论如何都不会用Python编写.)与头缓存不同,即使有头缓存,最终缓存也可以加速代码. list1和list2的条目之间没有数字重合.Ryser的算法在没有数字重合的情况下也很难解决这个问题,所以对于这种类型的输入我只看到两个加速:使用"全部"测试和"无"测试以及结束缓存来搜索搜索树的分支.

Answer 2

可能不是(没有简化的假设):你的问题是NP-Hard.这是对SUBSET-SUM的微不足道的缩减.设count_perms(L1, L2, x)表示函数"计算L2的排列数,使prodSum(L1,L2)<x"

SUBSET_SUM(L2,n): # (determine if any subset of L2 adds up to n)
    For i in [1,...,len(L2)]
        Set L1=[0]*(len(L2)-i)+[1]*i
        calculate count_perms(L1,L2,n+1)-count_perms(L1,L2,n)
        if result positive, return true
    Return false

因此,如果有办法有效地计算你的函数count_perms(L1, L2, x),那么我们将有一个有效的算法来计算SUBSET_SUM(L2,n).