Algoritmo para encontrar subconjunto dentro de dois conjuntos de números inteiros cujos montantes correspondem

Question

Eu estou procurando um algoritmo que pode levar dois conjuntos de números inteiros (positivos e negativos) e encontrar subconjuntos dentro de cada que tem a mesma soma.

O problema é semelhante ao subconjunto problema soma exceto que eu estou procurando para subconjuntos de ambos os lados.

Aqui está um exemplo:

Lista A {4, 5, 9, 10, 1}

Lista B {21, 7, -4, 180}

Assim, o único corresponder aqui é: {10, 1, 4, 9} <=> {21, 7, -4}

Alguém sabe se existem algoritmos existentes para este tipo das problemas?

Até agora, a única solução que tenho é uma abordagem de força bruta que tenta todas as combinações, mas ele executa em tempo exponencial e eu tive que colocar um limite rígido sobre o número de elementos a considerar para evitar que ele demorando muito .

A única solução que eu posso pensar é para executar um fatorial em ambas as listas e procurar igualdades lá, mas que ainda não é muito eficiente e tem exponencialmente mais como as listas de obter maiores.

Answer 1

O que outros disseram é verdade:

1. Este problema é NP-completo. Uma redução fácil é subconjunto de soma habitual. Você pode mostrar isso ao notar que um subconjunto dos montantes A para um subconjunto de B (não ambos vazios) somente se um subconjunto não vazio de uma união (-B) somas para zero.

2. Este problema é apenas fracamente NP-completos, em que é polinomial no tamanho das Números envolvidos, mas conjectura a ser exponencial em sua logaritmos . Isto significa que o problema é mais fácil do que o apelido de "NP-completo" poderia sugerir.

3. Você deve usar programação dinâmica.

Então o que estou a contribuir para esta discussão? Bem, o código (em Perl):

@a = qw(4 5 9 10 1);
@b = qw(21 7 -4 180);
%a = sums( @a );
%b = sums( @b );
for $m ( keys %a ) {
    next unless exists $b{$m};
    next if $m == 0 and (@{$a{0}} == 0 or @{$b{0}} == 0);
    print "sum(@{$a{$m}}) = sum(@{$b{$m}})\n";
}

sub sums {
    my( @a ) = @_;
    my( $a, %a, %b );
    %a = ( 0 => [] );
    while( @a ) {
        %b = %a;
        $a = shift @a;
        for my $m ( keys %a ) {
            $b{$m+$a} = [@{$a{$m}},$a];
        }
    %a = %b;
    }
    return %a;
}

Ela imprime

sum(4 5 9 10) = sum(21 7)
sum(4 9 10 1) = sum(21 7 -4)

assim, nomeadamente, há mais de uma solução que funciona em seu problema original!

Editar : User itzy corretamente assinalou que esta solução estava errado, e pior, de várias maneiras !! Sinto muito sobre isso e eu espero que abordou estas preocupações no novo código acima. No entanto, existe ainda um problema, ou seja, que para qualquer subconjunto de soma particular, imprime apenas uma das soluções possíveis. Ao contrário dos problemas anteriores, que eram erros straight-up, eu classificaria isso como uma limitação intencional. Boa sorte e cuidado com os erros!

Answer 2

Como o problema da soma do subconjunto, este problema é fracamente NP-completos, por isso tem uma solução que é executado em tempo polinomial (M), onde M é a soma de todos os números que aparecem no problema instância. Você pode conseguir isso com programação dinâmica. Para cada conjunto pode gerar todas as somas possíveis por enchimento de uma tabela binia 2-dimensional, onde "verdadeiro" na (k, m) significa que uma soma subconjunto m podem ser obtidos por colheita alguns elementos dos primeiros elementos de K do conjunto.

Você preenchê-lo de forma iterativa - você definir (k, m) para "true" se (k-1, m) é definido como "true" (obviamente, se você pode obter m de k-1 elementos, você pode obter -lo de k elementos por não escolher o k-th) ou se (k-1, md) é definido como "true", onde d é o valor de k-th elemento do conjunto (caso em que você escolher o k-th elemento).

Preencher a tabela você recebe todas as possíveis somas na última coluna (aquele que representa todo o conjunto). Faça isso para ambos os conjuntos e encontrar somas comuns. Você pode recuar os subconjuntos reais que representam as soluções invertendo o processo que você usou para preencher as tabelas.

Answer 3

Muito obrigado por todas as respostas rápidas!

A solução de programação dinâmica não é realmente diferente do approch exaustiva temos agora e eu acho que se nós precisamos a solução óptima que fazemos necessidade de considerar todas as combinações possíveis, mas o tempo que leva para gerar esta lista exaustiva dos montantes são demasiado longo.. Fiz um teste rápido e o tempo que leva para gerar todas as somas possíveis para x número de elementos muito rapidamente passar por cima de 1 min:

11 elements took - 0.015625 seconds
12 elements took - 0.015625 seconds
13 elements took - 0.046875 seconds
14 elements took - 0.109375 seconds
15 elements took - 0.171875 seconds
16 elements took - 0.359375 seconds
17 elements took - 0.765625 seconds
18 elements took - 1.609375 seconds
19 elements took - 3.40625 seconds
20 elements took - 7.15625 seconds
21 elements took - 14.96875 seconds
22 elements took - 31.40625 seconds
23 elements took - 65.875 seconds
24 elements took - 135.953125 seconds
25 elements took - 282.015625 seconds
26 elements took - 586.140625 seconds
27 elements took - 1250.421875 seconds
28 elements took - 2552.53125 seconds
29 elements took - 5264.34375 seconds

que para o problema de negócio que estamos tentando resolver não é realmente aceitável .. Eu vou voltar para a prancheta e ver se nós realmente precisa saber todas as soluções ou podemos simplesmente fazer com um ( o menor maior subconjunto /, por exemplo) em vez e espero que pode ajudar simplesmente o problema e fazer o meu algoritmo executar para expectaion.

Obrigado a todos o mesmo!

Answer 4

soma subconjunto é NP-completos e você pode reduzir polinomialmente seu problema para ele, para que o seu problema é NP-completo também.