将数字列表分为 2 个等和列表的算法

Question

有一个数字列表。
该列表将被分为 2 个大小相等的列表，并且总和相差最小。 必须打印总数。

<前><代码>#示例： >>>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/

Answer 1

动态编程就是您正在寻找的解决方案。

以 [4, 3, 10, 3, 2, 5] 为例：

X-Axis: Reachable sum of group.        max = sum(all numbers) / 2    (rounded up)
Y-Axis: Count elements in group.       max = count numbers / 2       (rounded up)

      1  2  3  4  5  6  7  8  9 10 11 12 13 14
 1  |  |  |  | 4|  |  |  |  |  |  |  |  |  |  |       //  4
 2  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
 3  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

      1  2  3  4  5  6  7  8  9 10 11 12 13 14
 1  |  |  | 3| 4|  |  |  |  |  |  |  |  |  |  |       //  3
 2  |  |  |  |  |  |  | 3|  |  |  |  |  |  |  |
 3  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

      1  2  3  4  5  6  7  8  9 10 11 12 13 14
 1  |  |  | 3| 4|  |  |  |  |  |10|  |  |  |  |       // 10
 2  |  |  |  |  |  |  | 3|  |  |  |  |  |10|10|
 3  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

      1  2  3  4  5  6  7  8  9 10 11 12 13 14
 1  |  |  | 3| 4|  |  |  |  |  |10|  |  |  |  |       //  3
 2  |  |  |  |  |  | 3| 3|  |  |  |  |  |10|10|
 3  |  |  |  |  |  |  |  |  |  | 3|  |  |  |  |

      1  2  3  4  5  6  7  8  9 10 11 12 13 14
 1  |  | 2| 3| 4|  |  |  |  |  |10|  |  |  |  |       //  2
 2  |  |  |  |  | 2| 3| 3|  |  |  |  | 2|10|10|
 3  |  |  |  |  |  |  |  | 2| 2| 3|  |  |  |  |

      1  2  3  4  5  6  7  8  9 10 11 12 13 14
 1  |  | 2| 3| 4| 5|  |  |  |  |10|  |  |  |  |       //  5
 2  |  |  |  |  | 2| 3| 3| 5| 5|  |  | 2|10|10|
 3  |  |  |  |  |  |  |  | 2| 2| 3| 5| 5|  |  |
                                       ^

12 是我们的幸运数字！ 回溯得到组：

12 - 5 = 7        {5}
 7 - 3 = 4        {5, 3}
 4 - 4 = 0        {5, 3, 4}

然后可以计算另一组：{4,3,10,3,2,5} - {5,3,4} = {10,3,2}

所有带有数字的字段都是可能的一袋解决方案。 选择右下角最远的一个。

顺便说一句：这被称为背包问题。

如果所有权重（w1，...，wn 和 W）都是
非负整数，背包
问题可以解决
使用动态伪多项式时间
编程。

Answer 2

新解决方案

这是一种采用启发式剔除的广度优先搜索。 树的深度限制为players/2。 玩家总分限制为总分/2。 玩家池为 100 人时，大约需要 10 秒才能解决。

def team(t):
    iterations = range(2, len(t)/2+1)

    totalscore = sum(t)
    halftotalscore = totalscore/2.0

    oldmoves = {}

    for p in t:
        people_left = t[:]
        people_left.remove(p)
        oldmoves[p] = people_left

    if iterations == []:
        solution = min(map(lambda i: (abs(float(i)-halftotalscore), i), oldmoves.keys()))
        return (solution[1], sum(oldmoves[solution[1]]), oldmoves[solution[1]])

    for n in iterations:
        newmoves = {}
        for total, roster in oldmoves.iteritems():
            for p in roster:
                people_left = roster[:]
                people_left.remove(p)
                newtotal = total+p
                if newtotal > halftotalscore: continue
                newmoves[newtotal] = people_left
        oldmoves = newmoves

    solution = min(map(lambda i: (abs(float(i)-halftotalscore), i), oldmoves.keys()))
    return (solution[1], sum(oldmoves[solution[1]]), oldmoves[solution[1]])

print team([90,200,100])
print team([2,3,10,5,8,9,7,3,5,2])
print team([1,1,1,1,1,1,1,1,1,9])
print team([87,100,28,67,68,41,67,1])
print team([1, 1, 50, 50, 50, 1000])

#output
#(200, 190, [90, 100])
#(27, 27, [3, 9, 7, 3, 5])
#(5, 13, [1, 1, 1, 1, 9])
#(229, 230, [28, 67, 68, 67])
#(150, 1002, [1, 1, 1000])

另请注意，我尝试使用 GS 的描述来解决此问题，但仅通过存储运行总计不可能获得足够的信息。 如果您同时存储了项目数和总数，那么它与此解决方案相同，只是您保留了不必要的数据。 因为你只需要保持n-1和n次迭代最多为numplayers/2。

我有一个基于二项式系数的旧详尽系数（查看历史）。 它很好地解决了长度为 10 的示例问题，但后来我看到比赛的人长度达到了 100。

Answer 3

问：给定一个整数多重集 S，有没有办法将 S 分成两个子集 S1 和 S2，使得数字的总和 S1中的数字等于S2中的数字之和？

A.设置分区问题。

祝你好运。 :)

Answer 4

好吧，您可以在多项式时间内找到百分比精度的解决方案，但要真正找到最佳（绝对最小差异）解决方案，该问题是 NP 完全的。 这意味着该问题不存在多项式时间解。 因此，即使数字列表相对较小，计算量也太大而无法解决。 如果您确实需要解决方案，请查看一些近似算法。

http://en.wikipedia.org/wiki/Subset_sum_problem

Answer 5

请注意，这也是一种启发式方法，我将排序移出函数。

 def g(data):
   sums = [0, 0]
   for pair in zip(data[::2], data[1::2]):
     item1, item2 = sorted(pair)
     sums = sorted([sums[0] + item2, sums[1] + item1])
   print sums

data = sorted([2,3,10,5,8,9,7,3,5,2])
g(data)

Answer 6

它实际上是 PARTITION，KNAPSACK 的一个特例。

它是 NP Complete，具有伪多项式 dp 算法。 伪多项式中的伪是指运行时间取决于权重的范围。

一般来说，在接受启发式解决方案之前，您必须首先确定是否存在精确解决方案。

Answer 7

您的方法不起作用的测试用例是

que = [1, 1, 50, 50, 50, 1000]

问题是您成对分析事物，在本例中，您希望所有 50 都位于同一组中。 不过，如果您删除配对分析方面并一次只执行一个条目，那么这个问题应该可以解决。

这是执行此操作的代码

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

if __name__=="__main__":
    que = [2,3,10,5,8,9,7,3,5,2]
    make_teams(que)
    que = [1, 1, 50, 50, 50, 1000]
    make_teams(que)

这给出了 27, 27 和 150, 1002 这对我来说是有意义的答案。

编辑：经过审查，我发现这实际上不起作用，尽管最后我不太确定为什么。 不过，我将在这里发布我的测试代码，因为它可能有用。 该测试只是生成具有相等总和的随机序列，将它们放在一起并进行比较（结果令人遗憾）。

编辑＃2：基于Unknown，[87,100,28,67,68,41,67,1]指出的示例，很明显为什么我的方法不'不工作。 具体来说，要解决此示例，需要将两个最大的数字都添加到同一序列中以获得有效的解决方案。

def make_sequence():
    """return the sums and the sequence that's devided to make this sum"""
    while 1:
        seq_len = randint(5, 200)
        seq_max = [5, 10, 100, 1000, 1000000][randint(0,4)]
        seqs = [[], []]
        for i in range(seq_len):
            for j in (0, 1):
                seqs[j].append(randint(1, seq_max))
        diff = sum(seqs[0])-sum(seqs[1])
        if abs(diff)>=seq_max: 
            continue
        if diff<0:
            seqs[0][-1] += -diff
        else:
            seqs[1][-1] += diff
        return sum(seqs[0]), sum(seqs[1]), seqs[0], seqs[1]

if __name__=="__main__":

    for i in range(10):
        s0, s1, seq0, seq1 = make_sequence()
        t0, t1 = make_teams(seq0+seq1)
        print s0, s1, t0, t1
        if s0 != t0 or s1 != t1:
            print "FAILURE", s0, s1, t0, t1

Answer 8

他们显然正在寻找动态规划背包解决方案。 因此，在我的第一次努力（我认为是一个相当好的原始启发式）和我的第二次努力（一个非常狡猾的精确组合解决方案，适用于较短的数据集，甚至适用于最多 100 个元素的集合，只要 的数量唯一值很低），我最终屈服于同行压力并编写了他们想要的一个（不是太难 - 处理重复条目是最棘手的部分 - 我基于它的底层算法仅在所有输入都是唯一的情况下才有效- 我很高兴long long足够大，可以容纳 50 位！）。

因此，对于我在测试前两项工作时汇总的所有测试数据和尴尬的边缘情况，它给出了相同的答案。 至少对于我用组合求解器检查的那些，我知道它们是正确的。 但我仍然因为一些错误的答案而提交失败！

我并不是要求任何人在这里修复我的代码，但如果有人能找到下面的代码生成错误答案的情况，我将非常感激。

谢谢，

Graham

PS 这段代码确实总是在时间限制内执行，但它距离优化很远。 我会保持简单，直到它通过测试，然后我有一些想法来加快它的速度，也许可以提高 10 倍或更多。

#include <stdio.h>

#define TRUE (0==0)
#define FALSE (0!=0)

static int debug = TRUE;

//int simple(const void *a, const void *b) {
//  return *(int *)a - *(int *)b;
//}

int main(int argc, char **argv) {
  int p[101];
  char *s, line[128];
  long long mask, c0[45001], c1[45001];
  int skill, players, target, i, j, tests, total = 0;

  debug = (argc == 2 && argv[1][0] == '-' && argv[1][1] == 'd' && argv[1][2] == '\0');

  s = fgets(line, 127, stdin);
  tests = atoi(s);
  while (tests --> 0) {

    for (i = 0; i < 45001; i++) {c0[i] = 0LL;}

    s = fgets(line, 127, stdin); /* blank line */
    s = fgets(line, 127, stdin); /* no of players */
    players = atoi(s);
    for (i = 0; i < players; i++) {s = fgets(line, 127, stdin); p[i] = atoi(s);}

    if (players == 1) {
      printf("0 %d\n", p[0]);
    } else {

    if (players&1) p[players++] = 0; // odd player fixed by adding a single player of 0 strength
    //qsort(p, players, sizeof(int), simple);

    total = 0; for ( i = 0; i < players; i++) total += p[i];
    target = total/2; // ok if total was odd and result rounded down - teams of n, n+1
    mask = 1LL << (((long long)players/2LL)-1LL);

    for (i = 0; i < players; i++) {
      for (j = 0; j <= target; j++) {c1[j] = 0LL;} // memset would be faster
      skill = p[i];
      //add this player to every other player and every partial subset
      for (j = 0; j <= target-skill; j++) {
        if (c0[j]) c1[j+skill] = c0[j]<<1;  // highest = highest j+skill for later optimising
      }
      c0[skill] |= 1; // so we don't add a skill number to itself unless it occurs more than once
      for (j = 0; j <= target; j++) {c0[j] |= c1[j];}
      if (c0[target]&mask) break; // early return for perfect fit!
    }

    for (i = target; i > 0; i--) {
      if (debug || (c0[i] & mask)) {
        fprintf(stdout, "%d %d\n", i, total-i);
        if (debug) {
          if (c0[i] & mask) printf("******** ["); else
          printf("         [");
          for (j = 0; j <= players; j++) if (c0[i] & (1LL<<(long long)j)) printf(" %d", j+1);
          printf(" ]\n");
        } else break;
      }
    }
    }
    if (tests) printf("\n");
  }
  return 0;
}

Answer 9

class Team(object):
    def __init__(self):
        self.members = []
        self.total = 0

    def add(self, m):
        self.members.append(m)
        self.total += m

    def __cmp__(self, other):
        return cmp(self.total, other.total)


def make_teams(ns):
    ns.sort(reverse = True)
    t1, t2 = Team(), Team()

    for n in ns:
        t = t1 if t1 < t2 else t2
        t.add(n)

    return t1, t2

if __name__ == "__main__":
    import sys
    t1, t2 = make_teams([int(s) for s in sys.argv[1:]])
    print t1.members, sum(t1.members)
    print t2.members, sum(t2.members)

>python two_piles.py 1 50 50 100
[50, 50] 100
[100, 1] 101

Answer 10

为了提高性能，您可以通过用运行总计替换append()和sum()来节省计算。

Answer 11

您可以使用以下方法收紧循环：

def make_teams(que):
    que.sort()
    t1, t2 = []
    while que:
        t1.append(que.pop())
        if sum(t1) > sum(t2):
            t2, t1 = t1, t2
    print min(sum(t1),sum(t2)), max(sum(t1),sum(t2))

Answer 12

由于列表必须相等，所以问题根本不是 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"

：我认为这也是一个错误的方法。 结果错误！

Answer 13

经过一番思考，对于不太大的问题，我认为最好的启发式方法是：

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 。

它几乎总是解决上述所有问题。

Answer 14

在之前的评论中，我假设所设置的问题是可以处理的，因为他们仔细选择了测试数据，以便在分配的时间内与各种算法兼容。 事实证明并非如此——相反，这是问题的限制——数字不高于450，并且最终集合不超过50个数字是关键。 这些与使用我在后面的文章中提出的动态编程解决方案解决问题兼容。 其他算法（启发式算法或组合模式生成器的详尽枚举）都不可能起作用，因为会有足够大或足够难的测试用例来破坏这些算法。 说实话，这相当烦人，因为其他解决方案更具挑战性，当然也更有趣。 请注意，在没有大量额外工作的情况下，动态编程解决方案只是说明对于任何给定的总和是否可以使用 N/2 找到解决方案，但它不会告诉您任一分区的内容。