Encontrar somatória de valores em array – php array

Pergunta:


Preciso desenvolver um algoritmo que encontre um valor específico da somatória de alguns elementos de um array. Ex: tenho um array com 50 valores distintos e tenho um dado valor “X”.

Sei que a soma da combinação de alguns elementos deste array resulta neste valor, o que preciso é saber quais são os elementos dentro desta lista que dá esta soma. Não posso usar algoritmos de combinação pois acima de 9 elementos já dá limite de memória excedido e tenho arrays bem maiores que isso para calcular.

O código que tenho até agora é este:

/**
 * Class Teste
 */
class Teste
{
    static $values  = array(15.92, 53.27, 244.28, 388.46, 3.14, 2.92, 18.22, 4.03);
    static $include = array();
//    static         $expected = 712.02;
    static         $expected = 297.55;
    static         $ok       = false;
    private static $_instance;

    /**
     * @return static
     */
    public static function instance()
    {
        return static::$_instance = static::$_instance ?: new static();
    }

    public function __construct()
    {
        while (!static::$ok) {
            reset(static::$include);
            static::removeItem(key(static::$include));
            static::calc();
        }
        var_export(static::sum());
    }

    public static function calc()
    {
        foreach (static::$values as $k => $v) {
            var_export(static::$include);
            if (round(static::$expected, 2) == round(static::sum(), 2)) {
                static::$ok = true;
                break;
            } else if (static::$expected > static::sum()) {
                static::addItem($k);
            }
            if (round(static::$expected, 2) < round(static::sum(), 2)) {
                static::removeItem($k);
            }
        }
    }

    public static function addItem($k)
    {
        if (!array_key_exists($k, static::$include)) {
            static::$include[$k] = round(static::$values[$k], 2);
        }
    }

    public static function removeItem($k)
    {
        unset(static::$include[$k]);
    }

    public static function sum()
    {
        return round(array_sum(static::$include), 2);
    }
}

Teste::instance();

Autor da pergunta Daniel

Resposta Daniel:

Solução otimizada:

Eu havia postado uma solução razoável (pode ser vista no histórico de edições da resposta), mas acabei pesquisando um pouco mais sobre esse tipo de combinação, e cheguei a esse código:

<?php
   static $values  = array( 15.92, 53.27, 244.28, 388.46, 3.14, 2.92, 18.22, 4.03 );
   static $expected = 297.55;
   static $precision = 100; /* para não ter problemas com ponto flutuante */

   $target = floor( $expected * $precision );
   $len = count( $values );
   for( $i = 1; $i < pow( 2, $len ); $i++ ) {
      $soma = 0;
      $set = array();
      for( $j = 0; $j < $len; $j++ ) {
         if( 1 << $j & $i ) {
            $set[] = $j;
            $soma += floor( $values[$j] * $precision );
         }
      }
      if( $soma == $target ) {
         // Estamos exibindo na tela apenas como demonstração. Se preferir pode armazenar.
         foreach( $set as $pos ) echo "[$pos]{$values[$pos]} ";
         echo " = $expected<br>n";
      }
   }
?>

Graças à um excelente algoritmo otimizado para combinações únicas que encontrei, foi possível deixar o código bem mais rápido e com pouco uso de memória.

As soluções que eu tentei anteriormente estouravam o timeout de 5 segundos no IDEONE, mesmo com somente oito valores no array. Esta aqui está funcionando extremamente bem neste tempo com essa quantidade de dados.

Veja funcionando no IDEONE.

Eu nunca programei em PHP na vida. Vou deixar um algoritmo aqui em javascript – peço que alguém crie uma nova resposta convertendo pra PHP (terá meu upvote).

Primeiro você pega todas as combinações possíveis (desconsiderando ordem). Já tinha feito algo parecido antes em outra resposta, mas fiz sem recursão aqui pra não estourar sua pilha 😉

var ar = [1, 2, 3, 4, 5, 6, 7, 8, 9];
var resultado = {
    "1": {}
};
for (var i = 0; i < ar.length; i++) {
    resultado["1"][ar[i] + ""] = [ar[i]];
}

var tamanhoMaximo = ar.length;

for (var tamanho = 2; tamanho <= tamanhoMaximo; tamanho++) {
    var tamanhoAtual = resultado[tamanho + ""] = {};
    var tamanhoAnterior = resultado[(tamanho - 1) + ""];
    for (var chave in tamanhoAnterior) {
        var tempAr = tamanhoAnterior[chave];
        for (var i = 0; i < ar.length; i++) {
            if (tempAr.indexOf(ar[i]) == -1) {
                var novoAr = tempAr.slice();
                novoAr.push(ar[i]);
                novoAr.sort();
                tamanhoAtual[novoAr.join(",")] = novoAr;
            }
        }
    }
}
resultado;

Agora é só percorrer o mapa e ver quais combinações dão sua soma.

function encontraCombinacoes (mapa, procurado) {
    for (var chave in mapa) {
        for (var subchave in mapa[chave]) {
            var array = mapa[chave][subchave];
            var soma = 0;
            for (var i = 0; i < array.length; i++) {
                soma += array[i];
            }
            if (soma == procurado) {
                console.log(subchave);
            }
        }
    }
}
encontraCombinacoes(resultado, 6); // Só de exemplo

Note que você já podia verificar as somas no primeiro código. O que fiz aqui acumula combinações que podem passar do valor que você procura. Você pode deixar o algoritmo mais eficiente já contando as somas enquanto monta as combinações.

Quando alguém converter isso aqui pra PHP, posso apagar esta resposta.

edit: tem um erro no algoritmo e ele não pega todas as combinações (ficam faltando uns 20% delas). Assim que puder eu ajeito – ou alguém pode encontrar o erro e corrigir antes!. Corrigi!

Esta solução foi a mais eficaz para arrays com bastantes elementos.

$notas = [
  999 => 8,
  456 => 4,
  789 => 5,
  123 => 2,
];

asort($notas);

function remove_maiores_que($total, $numeros) {
    return array_filter($numeros, function($n) use ($total) {
        return $n <= $total;
    });
}

function find_soma($total, $numeros) {
    if ($total <= 0) return array();

    // primeiro remove os numeros maiores que o total buscado
    $numeros = remove_maiores_que($total, $numeros);

    $sum = array_sum($numeros);

    // se a soma de todos elementos do array for inferior ao total, não adianta procurar
    if ($sum < $total) {
        return array();
    }

    // já achou o array
    if ($sum == $total) {
        return $numeros;
    }

    // remove o maior e procura soma do restante
    while( end($numeros) ) { // enquanto tiver numeros no array
        // remove o maior e sua respectiva chave
        $key = key($numeros);
        $n = array_pop($numeros);

        // verifica se o numero já é igual ao total
        if ($n == $total) {
            return array($key => $n);
        }

        // no array que sobrou, procura pela diferença do total e o número maior removido acima
        $sub_total = $total - $n;

        $soma = find_soma($sub_total, $numeros);

        // se a soma não for vazia, então encontrou a sub soma
        if ( ! empty($soma) ) {
            // adiciona o numero atual no final da soma e retorna
            $soma[$key] = $n;
            return $soma;
        }
    }

    // retorna array vazio indicando que não encontrou nenhuma soma
    return array();
}

find_soma(6, $notas);

Fonte

Related Posts:

Qual a diferença entre AppCompatActivity e Activity? – android android-activity
Pergunta: Qual a diferença da AppCompatActivity para Activity ? A partir de qual versão a AppCompatActivity foi adicionada ao Android? Autor da pergunta Luhhh A diferença reside ...
Como abreviar palavras em PHP? – php string
Pergunta: Possuo informações comuns como nome de pessoas e endereços, e preciso que elas contenham no máximo 30 caracteres sem cortar palavras. Exemplo: 'Avenida Natalino João Brescansin' ...
Qual é a finalidade de um parêntese vazio numa declaração Lambda? – c# expressões-lambda característica-linguagem
Pergunta: Criei um exemplo de uma declaração Lambda sem argumentos, entretanto, estou com duvidas referente a omissão do parêntese vazio () na declaração. Veja o exemplo: class ...
Boas práticas para URI em API RESTful – api rest restful
Pergunta: Estou com dúvida em relação às URIs de alguns recursos da api que estou desenvolvendo. Tenho os recursos projetos e atividades com relação 1-N, ...
Dúvidas sobre a integração do MySQL com Java – java mysql netbeans
Pergunta: Estou criando um sistema no NetBeans, utilizando a linguagem Java e o banco de dados MySQL. Escrevi o seguinte código para realizar a conexão ...
Qual é a finalidade da pasta Model do framework Inphinit? – php inphinit
Pergunta: No Inphinit micro-framework existe a pasta Model que fica dentro da pasta application, e nela é onde ficam as classes, mas eu estou muito ...
Uso do ‘@’ em variáveis – javascript typescript coffeescript
Pergunta: Vejo em algumas linguagens que compilam para javascript, como TypeScript e CoffeeScript, o uso do @ em variáveis, como também, casos em que o ...
Qual tamanho máximo um arquivo JSON pode ter? – json arquivo
Pergunta: Vou dar um exemplo para conseguir explicar minha duvida: Preciso recuperar informação de imagens vindas de uma API, esse banco de imagens me retorna JSON's ...
O que é Teste de Regressão? – terminologia engenharia-de-software testes
Pergunta: Na matéria de Teste de Software o professor abordou um termo chamado Teste de Regressão, isto dentro da disciplina de teste de software. Sendo ...
O que é um construtor da linguagem? – php característica-linguagem
Pergunta: Em PHP, já li e ouvi várias vezes a respeito dos Construtores da Linguagem. Os casos que sempre ouvi falar deles foi em casos ...
Função intrínseca para converter numérico para string – cobol
Pergunta: Estou a tentar saber se existe alguma função intrínseca do COBOL para converter um data numérico para string sem precisar usar a cláusula REDEFINES: ( ...
Porque usar implements? – java android
Pergunta: Qual a diferença entre usar btn.setOnClickListener(new OnClickListener() { e public class MainActivity extends Activity implements OnClickListener{ Estive fazendo um curso de Android e meu professor falou que ...
O que é XHTML e quando deve ser usado? – html xml xhtml
Pergunta: O que eu sei é que o XHTML precisa ser XML válido. Isso implica, por exemplo, que todas as tags precisam ser fechadas. Por ...
Uma placa aceleradora de vídeo pode melhorar o desempenho não-gráfico? [fechada] – desempenho
Pergunta: Para desenvolver em Ruby on Rails, eu utilizo aqui uma máquina virtual do VirtualBox com Ubuntu Server 14.04 sem interface gráfica instalada. Recentemente descobri uma ...
Concat() VS Union() – c# .net
Pergunta: Qual a diferença entre Concat() e Union() ? Quando usar Concat() e quando usar Union() ? Somente pode ser usado em list ? ...

Deixe uma resposta

O seu endereço de email não será publicado. Campos obrigatórios marcados com *