江苏龙网

  1. 首页 > 生活 > >

n个有重复数，求其一种排列使得前缀和绝对值的最大值最小，有较好的算法吗

补充一些细节。首先证明“子集和问题”可以归约为“均分问题”。子集和问题是给定 n 个正整数和一个正整数 m ，问能否从 n 个数中取出一些数使其和为 m 。用 (A, m) 表示子集和问题的输入，其中 A 是长度为 n 的正整数列。均分问题是给定 n 个正整数，问能否将这些数分成两部分，使它们各自的和相等。用 A 表示均分问题的输入，其中 A 是长度为 n 的正整数列。注意均分问题显然可以归约为子集和问题（不过这不是我们需要的），但反过来则需要说明。任给一个子集和问题的输入 I=(A, m) ，计算 A 中所有数之和 S ，将 J=A?{S+m+1, 2S-m+1} 作为均分问题的输入，则 I 满足子集和问题，当且仅当 J 满足均分问题。这就完成了将子集和问题归约为均分问题的过程。接下来将均分问题归约为题主所述的问题。题主的问题不是判定性问题，但是很容易找到相应的判定性问题：给定 n 个整数和一个整数 m ，问能否将 n 个数重排，使新数列前缀和绝对值的最大值小于等于 m 。不妨将该问题称为“前缀和问题”。用 (A, m) 表示前缀和问题的输入，其中 A 是长度为 n 的正整数列。之后将均分问题归约为前缀和问题，这个其他回答已经提到了。任给一个均分问题的输入 I=A ，计算 A 中所有数之和 S ，将 J=(A?{-S}, S/2) （其中 S/2 取下整）作为前缀和问题的输入，则 I 满足均分问题，当且仅当 J 满足前缀和问题。归约过程完成。因为子集和问题是 NPC 问题，所以前缀和问题是 NP-hard 问题（实际上前缀和问题也是 NP 问题，只要将 n 个数重排的顺序作为证书即可；因此，前缀和问题是 NPC 问题），从而不太可能在多项式时间内解决。题主的问题比“前缀和问题”（指刚刚提到的判定性问题）要强，因为若求得前缀和绝对值最大值的最小值，立即可以解决“前缀和问题”。所以题主的问题也不太可能在多项式时间内解决。
■网友
我来解释一下 @赵金昊 构造的例子。
假设已知的数中有且仅有一个负数 -2N，另外的数都是正数，且和为 2N。
如果这些正数中有若干个相加等于 N，那么就可以构造这样一个排列：相加等于 N 的数排在前面，然后排 -2N，再把另外一些数排在后面。这样，「前缀和的绝对值」最大是 N。
如果这些正数中没有任意一个子集相加等于 N，则上面这件事做不到，「前缀和的绝对值」必然在某个时刻大于 N。
而「判断一些数中有没有一个子集相加等于给定值」（称为「子集和问题」）是一个 NPC 问题，题主的问题可以化归为子集和问题，所以没有多项式时间的解。

■网友
NPC的，别想啦。搞个-2N，以及若干个和为2N的数，不是分分钟变成子集和问题嘛。所以解题思路只有一种，就是看数的大小。如果不超过10的话还是可做的……
■网友
【n个有重复数，求其一种排列使得前缀和绝对值的最大值最小，有较好的算法吗】 数据范围小的时候可以考虑暴搜O(n!)或者去dp一下——dp，保存值为前缀最大值O(2^n*n)。

■网友
既然是NPC那我就可以放心大胆推荐退火和遗传了
■网友
感觉退火可做。


    推荐阅读


    上一篇：做一个家具、家居电子商务网站，挑战点在哪核心的竞争要素在哪

    下一篇：Lol使自己的队伍获得胜利的关键是啥?