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

Ответ 1

Новое решение

Это первый поиск с эвристикой. Дерево ограничено глубиной игроков /2. Предел суммирования игрока - totalalscores/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.

Ответ 2

Динамическое программирование - это решение, которое вы ищете.

Пример с [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 наш счастливый номер! Backtracing для получения группы:

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}

Все поля с числом возможных решений для одного мешка. Выберите тот, который наиболее удален в нижнем правом углу.

BTW: он назвал проблемой ранца.

Если все веса (w1,..., wn и W) являются неотрицательные целые числа, рюкзак проблема может быть решена в псевдополиномиальное время с использованием динамического программирование.

Ответ 3

Хорошо, вы можете найти решение для процентной точности в полиномиальное время, но чтобы найти оптимальное (абсолютное минимальное различие) решение, проблема NP-полная. Это означает, что для решения проблемы не существует полиномиального решения времени. В результате даже с относительно небольшим списком чисел он слишком усложняется для решения. Если вам действительно нужно решение, взгляните на некоторые из алгоритмов аппроксимации для этого.

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

Ответ 4

Q. Учитывая многомножество S целых чисел, существует способ разделить S на два подмножества S1 и S2 такие, что сумма чисел в S1 равна сумме чисел в S2?

A. Задайте проблему раздела.

Самое удачное приближение.:)

Ответ 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)

Ответ 6

В тестовом примере, где ваш метод не работает,

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

Ответ 7

Это на самом деле РАЗРЕШЕНИЕ, частный случай KNAPSACK.

Это NP Complete, с псевдополиномиальными dp-алгоритмами. Псевдо в псевдополином относится к тому, что время выполнения зависит от диапазона весов.

В общем, вам придется сначала решить, есть ли точное решение, прежде чем вы сможете принять эвристическое решение.

Ответ 8

Они, очевидно, ищут решение для динамического программирования. Итак, после моего первого усилия (довольно хорошая оригинальная эвристика, о которой я думал), и моего второго усилия (действительно скрытого точного комбинаторного решения, которое работало на коротких наборах данных и даже для наборов до 100 элементов, если количество уникальных значений было низкий), я, наконец, поддался давлению со стороны сверстников и написал то, что они хотели (не слишком сложно - обработка дублированных записей была самой сложной частью - основной алгоритм, на котором я основывался, работает только если все входы уникальны - я уверен, рад, что длинный длинный достаточно большой, чтобы держать 50 бит!).

Итак, для всех тестовых данных и случаев неудобного края, которые я собрал во время тестирования моих первых двух усилий, он дает тот же ответ. По крайней мере, для тех, которые я проверил с помощью комбинаторного решателя, я знаю, что они верны. Но я все еще не получаю представление с неправильным ответом!

Я не прошу кого-нибудь исправить мой код здесь, но я был бы очень благодарен, если бы кто-нибудь мог найти случай, для которого код ниже порождает неправильный ответ.

Спасибо,

Грэхэм

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;
}

Ответ 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

Ответ 10

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

Ответ 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))

Ответ 12

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

Я разбил отсортированный список с шаблоном t1 < -que (1-й, последний), 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"

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

Ответ 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, если проблема больше.

Он решает всю проблему, упомянутую выше, в основном все время.

Ответ 14

В более раннем комментарии я предположил, что заданная проблема является приемлемой, поскольку они тщательно выбрали тестовые данные для совместимости с различными алгоритмами за время, выделенное. Это оказалось не так - вместо этого это проблемы - числа не выше 450, а окончательный набор не более 50 чисел - это ключ. Они совместимы с решением проблемы с использованием решения динамического программирования, которое я изложил в более позднем посте. Ни один из других алгоритмов (эвристика или исчерпывающее перечисление генератором комбинаторных шаблонов) не может работать, потому что будут тестовые случаи достаточно большие или достаточно жесткие, чтобы разбить эти алгоритмы. Это довольно раздражает, если честно, потому что эти другие решения более сложны и, конечно, веселее. Обратите внимание, что без большой дополнительной работы решение динамического программирования просто указывает, возможно ли решение с N/2 для любой заданной суммы, но оно не сообщает вам содержимое любого раздела.