Combinar valores de lista até chegar em um total específico da maneira mais eficiente possível.

[thiagotps]

Olá, boa noite!

Já pesquisei a solução de um problema na internet mas não obtive sucesso.

A empresa que eu trabalho recebeu um crédito de 5000 reais numa negociação. Temos diversas duplicatas a vencer que seriam abatidas com este crédito, com valores menores que este, ex: "100, 200, 150, 230, 400, 500, 600..." (os valores são bem mais "quebrados", apenas para ilustrar!)

Existe alguma forma de eu selecionar dentro deste conjunto de duplicatas, a melhor combinação possível de forma que todos os valores selecionados somados cheguem ao valor total do crédito recebido ou o mais próximo possível deste? O número de duplicatas selecionadas não importa, e sim a aproximação ao valor, já que não poderemos utilizar o saldo restante pra nada.

Alguém poderia explicar se é possível e como fazer?

Obrigado!

Thiago

[haroflow]

Olá,

Não conheço uma forma de fazer isso matematicamente... Também gostaria de saber como resolver esses problemas de otimização.

Tenho uma leve sensação de que você é programador, estou certo? =P

Fiz um teste em javascript, na força bruta mesmo, sem muita otimização... se quiser dar uma olhada está nos anexos. O único problema é que o processamento pra N contas fica N! (fatorial) né... Testei com saldo 5000 e umas 17 contas e funcionou, acima disso não sei como vai se comportar.


Até mais!

Anexos

otimizacaoContas.rar

(240.45 KiB) Transferido 274 Vezes