动态规划:产品总和

qanimi 发布于 2019-11-10 algorithm 最后更新 2019-11-10 12:10 261 浏览

假设您有两个长度相同的列表L1和L2,我们将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]的整数列表,这是不可能的。我仍然对假设这种约束的解决方案感兴趣。
已邀请:

tvelit

赞同来自:

内容太长未翻译

aet

赞同来自:

可能不是(没有简化的假设):你的问题是NP-Hard。这是SUBSET-SUM的简单减少。设count_perms(L1, L2, x)表示函数“计算L2的排列数,使得prodSum(L1,L2)

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)。

vdicta

赞同来自:

这也证明是一个抽象的代数问题。这对我来说已经有一段时间了,但这里有一些事情要开始。关于以下内容没有什么特别重要的(它都是非常基本的;扩展了每个组与排列组同构的事实),但它提供了一种不同的方式来查看问题。 我将尝试坚持相当标准的表示法:“x”是一个向量,“x i ”是x的i th 组成部分。如果“L”是列表,则L是等效矢量。 “1 n ”是一个所有分量= 1的向量。自然数set的集合被认为是正整数。 “[a,b]”是从a到b的整数集,包括端点。 “θ(x,y)”是由x和y形成的角度 注意prodSum是点积。该问题等同于找到由L2上的操作(置换元素)生成的所有向量L,使得θ(L1,L)小于给定角度α。该操作相当于通过子空间通过显示反映ℕ n 中的一个点:

< ℕn | (xixj-1)(i,j) ∈ A >
其中i和j在[1,n]中,A至少有一个元素且没有(i,i)在A中(即A是[1,n] 2 其中| A |> 0)。更明确地(并且更模糊地)陈述,子空间是一个或多个组件等于一个或多个其他组件的点。反射对应于其列是所有标准基矢量的矩阵。 让我们将反射组命名为“RP n ”(它应该有另一个名称,但内存失败)。 RP n 与对称组S n 同构。从而
|RPn| = |Sn| = n!
在3维中,这给出了一组6阶。反射组是D 3 ,三角形对称组,作为立方体对称组的子组。事实证明,您也可以通过沿着1 n 的线绕着π/ 3的增量旋转L2来生成点。这是模块化组ℤ 6 ,这指出了一个可能的解决方案:找到一组n阶!使用最少数量的生成器并使用它来生成L2的排列作为序列,其中L2增加然后减小角度。从那里,我们可以尝试生成具有θ(L1,L) n 。 RP' 4 由4个子空间构成,这些子空间与ℤ 6 同构。更一般地,RP' n 由n个子空间构成,这些子空间与RP' n-1 同构。 这是我的抽象代数肌肉真正开始失败的地方。我会继续努力进行施工,但是Managu的回答并没有留下太多希望。我担心将RP 3 减少到ℤ 6 是我们可以做出的唯一有用的减少。

wsed

赞同来自:

看起来如果l1和l2都是高 - 低(或低 - >高,无论如何,如果它们具有相同的顺序),则结果最大化,如果它们是有序的,则结果最小化,而其他秩序的改变似乎遵循一些规则;在连续的整数列表中交换两个数字总是将总和减少一个固定的数量,这似乎与它们的距离相关(即交换1和3或2和4具有相同的效果)。这只是一点点麻烦,但想法是有一个最大值,一个最小值,如果它们之间有一些预先指定的值,那么就有办法计算使这种情况成为可能的排列(尽管如果;列表不是均匀间隔,然后没有。好吧,不是我知道的。如果l2是(1 2 4 5)交换1 2和2 4会有不同的效果)