Algoritmo para dividir uma lista de números em 2 listas de montante igual
https://stackoverflow.com/questions/890171
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Há uma lista de números.
A lista deve ser dividido em 2 listas de tamanhos iguais, com uma diferença mínima na soma. As somas têm de ser impressa.
#Example:
>>>que = [2,3,10,5,8,9,7,3,5,2]
>>>make_teams(que)
27 27
Existe um erro no algoritmo de código a seguir por algum caso?
Como faço para otimizar e / ou pythonize isso?
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"
A pergunta é de http://www.codechef.com/problems/TEAMSEL/
Solução
New Solution
Esta é uma busca em largura primeiro com heurísticas abate. A árvore é limitada a uma profundidade de jogadores / 2. O limite soma jogador é totalscores / 2. Com um grupo de jogadores de 100, que levou cerca de 10 segundos para resolver.
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])
Observe também que eu tentava resolver isso usando descrição de GS, mas é impossível obter informação suficiente simplesmente armazenar os totais em execução. E se você armazenou ambos o número de itens e totais, em seguida, seria o mesmo que esta solução, exceto que você manteve os dados desnecessários. Porque você só precisa manter os n-1 e n iterações até numplayers / 2.
Eu tive uma uma exaustiva de idade com base no coeficiente binomial (olhar na história). Ele resolveu os problemas de exemplo de comprimento de 10 muito bem, mas viu então eu que a competição tinha pessoas de até length 100.
Outras dicas
dinâmica programação é a solução que você está procurando.
Exemplo com [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 é o nosso número da sorte! Backtracing para obter o grupo:
12 - 5 = 7 {5}
7 - 3 = 4 {5, 3}
4 - 4 = 0 {5, 3, 4}
O outro conjunto pode então ser calculada: {4,3,10,3,2,5} - {5,3,4} = {10,3,2}
Todos os campos com um número são as soluções possíveis para um saco. Escolha aquela que está mais no canto inferior direito.
BTW:. É o chamado mochila de problemas
Se todos os pesos (w1, ..., wn e W) são inteiros não negativos, a mochila problema pode ser resolvido em tempo pseudo-polinomial usando dinâmico programação.
Bem, você pode encontrar uma solução para uma precisão percentual em tempo polinomial, mas para realmente encontrar a solução ideal (absoluto diferença mínima), o problema é NP-completo. Isso significa que não existe uma solução em tempo polinomial para o problema. Como resultado, mesmo com um relativamente pequena lista de números, é muito computação intensiva para resolver. Se você realmente precisa de uma solução, dar uma olhada em alguns dos algoritmos de aproximação para isso.
Q. Dado um multiset S de inteiros , há uma maneira de partição S em dois subconjuntos S1 e S2 tal que a soma dos números em S1 é igual à soma dos números em S2?
A. Set Partition problema.
Melhor de aproximar sorte. :)
Note que também é uma heurística e eu nos mudamos o tipo para fora da função.
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)
É realmente PARTITION, um caso especial da mochila.
É NP Complete, com algoritmos dp pseudo-polinomial. O pseudo em pseudo-polinomial refere-se ao fato de que o tempo de execução depende da gama dos pesos.
Em geral, você terá que decidir primeiro se existe uma solução exata antes de poder admitir uma solução heurística.
Um caso de teste onde o seu método não funcionar é
que = [1, 1, 50, 50, 50, 1000]
O problema é que você está analisando as coisas em pares, e, neste exemplo, você quer que todos os anos 50 para estar no mesmo grupo. Isso deve ser resolvido apesar de se remover o aspecto análise par e apenas fazer uma entrada de cada vez.
Aqui está o código que faz isso
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)
Esta dar 27, 27 e 150, 1002, que são as respostas que fazem sentido para mim.
Editar: Na revisão, eu acho que isso não é realmente o trabalho, embora, no final, eu não estou muito certo porquê. Vou postar meu código de teste aqui, porém, como ele pode ser útil. O teste apenas gera seqüência aleatória que tem somas iguais, coloca-los juntos e compara (com resultados tristes).
Edit # 2: Com base no exemplo apontado por Unknown, [87,100,28,67,68,41,67,1], é claro por que o meu método não funciona. Especificamente, para resolver este exemplo, as duas maiores números precisam tanto ser adicionado à mesma seqüência para obter uma solução válida.
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
Eles são, obviamente, à procura de uma solução de programação mochila dinâmico. Então, depois de minha primeira tentativa (um bom bastante original eu pensamento heurística), e meu segundo trabalho (uma solução realmente furtivo exata combinatória que trabalhou para conjuntos de dados shortish, e até mesmo para conjuntos de até 100 elementos, desde que o número de única valores foi baixa), eu finalmente sucumbiu à pressão dos pares e escreveu o que queria (não muito difícil - manipulação de entradas duplicadas foi a parte mais complicada - o algoritmo I subjacente baseou em só funciona se todas as entradas são únicos - estou certo prazer que long long é grande o suficiente para armazenar 50 bits)
!.Assim, para todos os dados de teste e casos de ponta desajeitados eu juntos ao testar meus dois primeiros esforços, dá a mesma resposta. Pelo menos para os que eu verificados com o solver combinatória, eu sei Eles estão corretos. Mas eu ainda estou falhando a apresentação com alguma resposta errada!
Eu não estou pedindo para qualquer um para corrigir o meu código aqui, mas eu ficaria muito grato se alguém pode encontrar um caso para o qual o código abaixo gera a resposta errada.
Obrigado,
Graham
PS Este código nem sempre executar dentro do limite de tempo, mas é muito a partir otimizado. eu estou mantendo-o simples até que ele passa no teste, então eu tenho algumas idéias para acelerá-lo, talvez por um fator de 10 ou mais.
#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;
}
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
Para obter o desempenho que você salvar cálculos substituindo append () e sum () com totais em execução.
Você poderia apertar o laço um pouco usando o seguinte:
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))
Uma vez que as listas têm de me igualar o problema não é NP em tudo.
Eu dividir a lista ordenada com o padrão t1 <-que (1º, último), t2 <-que (2, última-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"
Editar : Acho que este é também um método errado. resultados errados!
Depois de algum pensamento, para não muito grande problema, eu acho que o melhor tipo de heurística será algo como:
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
Você pode ajustar nb_iter se o problema é maior.
Ele resolve todo o problema mencionado acima principalmente todos os tempos.
Em um comentário anterior I hipótese de que o problema como set foi tratável porque tinham escolhido cuidadosamente os dados de teste para ser compatível com vários algoritmos dentro do tempo alocado. Este acabou por não ser o caso - em vez disso, é a restrições do problema - números não superior a 450 e um conjunto final não maior do que 50 números é a chave. Estes são compatíveis com a solução do problema usando a solução de programação dinâmica que eu colocar em um post mais tarde. Nenhum dos outros algoritmos (heurística, ou enumeração exaustiva por um gerador de padrão combinatória) pode funcionar porque haverá casos de teste suficientemente grande ou forte o suficiente para quebrar os algoritmos. É muito chato para ser honesto, porque essas outras soluções são mais difíceis e certamente mais divertido. Note-se que, sem um monte de trabalho extra, a solução de programação dinâmica apenas diz se uma solução é possível com N / 2 para qualquer soma, mas não dizer-lhe o conteúdo de qualquer partição.
