将一个数字列表分成两个等和列表的算法

Question

将一个数字列表分成两个等和列表的算法

pythonalgorithmdynamic-programmingnp-completeknapsack-problem

25

有一个数字列表。需要将该列表分成两个大小相等的列表，使它们的和之差最小。需要打印这两个列表的和。

#Example:
>>>que = [2,3,10,5,8,9,7,3,5,2]
>>>make_teams(que)
27 27

以下代码算法在某些情况下是否存在错误？如何进行优化和/或Python化？

def make_teams(que):
    que.sort()
    if len(que)%2: que.insert(0,0)
    t1,t2 = [],[]
    while que:
        val = (que.pop(), que.pop())
        if sum(t1)>sum(t2):
            t2.append(val[0])
            t1.append(val[1])
        else:
            t1.append(val[0])
            t2.append(val[1])
    print min(sum(t1),sum(t2)), max(sum(t1),sum(t2)), "\n"

这个问题来源于 http://www.codechef.com/problems/TEAMSEL/

- lprsd

2

这是一种装箱问题的变体吗？我记得这是一个NP完全问题。 - Jerry Penner

3

que = [1,50,50,100]应该得到100和101两个队伍。我觉得你的算法会得到51和150。 - Alex B

1

@S.Lott 这是一个编程竞赛中的练习问题。这是参考链接：http://www.codechef.com/problems/TEAMSEL/ 据我所知，我的理解是正确的。但系统标记为不正确。 - lprsd

2

@Alex B：当我运行它时，我得到了100和101。 - Glenn

@Alex B：根据您的输入，我正确地得到了100和101。 - lprsd

@becomingGuru，看看我的解决方案，我认为你会喜欢的。 - Unknown

14个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nick Dandoulakis · Answer 1

既然列表必须相等，那么这个问题根本不是 NP 问题。

我用模式 t1<-que(1st, last), t2<-que(2nd, last-1) 来分割排序后的列表……

def make_teams2(que):
    que.sort()
    if len(que)%2: que.insert(0,0)
    t1 = []
    t2 = []
    while que:
        if len(que) > 2:
            t1.append(que.pop(0))
            t1.append(que.pop())
            t2.append(que.pop(0))
            t2.append(que.pop())
        else:
            t1.append(que.pop(0))
            t2.append(que.pop())
    print sum(t1), sum(t2), "\n"

编辑：我想这也是一种错误的方法。结果不正确！

- odwl · Answer 2

经过一些思考，对于不太大的问题，我认为最好的启发式方法将是类似于以下内容：

import random
def f(data, nb_iter=20):
  diff = None
  sums = (None, None)
  for _ in xrange(nb_iter):
    random.shuffle(data)
    mid = len(data)/2
    sum1 = sum(data[:mid])
    sum2 = sum(data[mid:])
    if diff is None or abs(sum1 - sum2) < diff:
      sums = (sum1, sum2)
  print sums

如果问题更大，您可以调整nb_iter参数。

它可以大多数时间解决上述所有问题。

- Graham Toal · Answer 3

在早期的评论中，我假设问题是可解的，因为他们精心选择了与所分配的时间内的各种算法兼容的测试数据。但事实并非如此——问题的限制条件是关键——数字不超过450，最终集合不超过50个数字。这些条件与我在后来的帖子中提出的动态规划解决方案相兼容。其他算法（启发式算法或组合模式生成器的穷举枚举）都不可能起作用，因为会有足够大或足够难的测试用例来破坏这些算法。说实话，这相当令人恼火，因为那些其他解决方案更具挑战性，肯定更有趣。请注意，除非进行大量额外的工作，否则动态规划解决方案只能说明是否存在一个给定总和的N/2的解决方案，但它不能告诉您任何一个分区的内容。

- Glenn · Answer 4

为了提高性能，您可以通过使用累加器来替换append()和sum()函数来节省计算时间。