Алгоритм деления списка чисел на 2 списка равных сумм - PullRequest
Новая
       42

Алгоритм деления списка чисел на 2 списка равных сумм

23 голосов
/ 21 мая 2009

Есть список номеров.

Список должен быть разделен на 2 одинаковых по размеру списка с минимальной разницей в сумме. Суммы должны быть напечатаны. 

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

Есть ли ошибка в следующем алгоритме кода для некоторого случая?

Как мне оптимизировать и / или питонизировать это? 

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/

Ответы [ 14 ]

0 голосов
/ 21 мая 2009

Поскольку списки должны быть равны, проблема вовсе не в NP.

Я разделил отсортированный список по шаблону t1 <-que (1st, last), t2 <-que (2nd, last-1) ... </p> 

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"

Редактировать : Полагаю, это тоже неправильный метод. Неверные результаты!

0 голосов
/ 21 мая 2009

Вы можете немного затянуть петлю, используя следующее: 

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))
0 голосов
/ 21 мая 2009

Для повышения производительности вы сохраняете вычисления, заменяя append () и sum () на промежуточные суммы.

0 голосов
/ 21 мая 2009 
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
Страница:
...