Qual algoritmo devo usar para encontrar a solução mais próxima para um determinado total usando uma lista de inteiros?

Question

Meu problema é este:

digamos que eu tenho uma lista arbitrária de inteiros A [2013, 54, 3, 32 1, 23 ...]

Qual é a melhor estratégia para descobrir quais desses números devo adicionar para ter uma soma igual ou mais próxima de um determinado número?

Obviamente, há sempre o método de força bruta, mas estou interessado em saber se há um mais otimizado.

Answer 1

Ao embalar a bagagem em um carro, você coloca os maiores itens primeiro e depois se encaixam nos itens menores ao redor deles. Por analogia, uma abordagem heurística ao seu problema é começar com o membro do seu conjunto que é o mais grande possível enquanto ainda é menor do que o alvo. Em seguida, repita o processo para a diferença entre você total e seu alvo e assim por diante. Isso é conhecido como um algoritmo ganancioso .

Por exemplo, se o seu conjunto é $ \ {2,3,5,8,13,21, 34 \} $ e o destino é $ 32 $ , comece com $ 21 $ (o maior valor menor que $ 32 $ ), em seguida, adicione $ 8 $ (porque este é o grande valor menor que $ 32-21= 11 $ < / span>) e, em seguida, adicione $ 3 $ .

Um algoritmo ganancioso é rápido e simples, mas nem sempre lhe dará a melhor solução. Por exemplo, se o seu conjunto é $ \ {1, 5, 23, 26 \} $ e você segmentar é $ 30 $ então o algoritmo ganancioso dá $ 26 + 1= 27 $ , enquanto a melhor solução é $ 23 + 5 + 1= 29 $ .

Answer 2

O problema é NP-completo, mas polinômio no valor do número dado, com um grau polinomial bastante baixo. É difícil se os números envolvidos são grandes.

Classificação de menor para maior e adicionar até que nenhum número de números não seja muito inteligente, porque provavelmente será um número bastante grande que não se encaixa, e você não se aproximará da soma desejada. Muito melhor para classificar do maior para menor e adicionar os maiores números primeiro.

Agora, se você tiver itens com uma soma fechar para s, você pode tentar melhorar isso. Por exemplo, se sua soma é muito pequena por 117, mas o menor item não utilizado é 317, você tentaria se você tiver um item x na sua lista e um item Y não na lista, onde Y é cerca de 200 menores que X - swap x contra y, adicione o item do tamanho 317. Mesmo um algoritmo simples provavelmente vai encontrar boas melhorias.

Um método completamente diferente: Deixe a soma desejada ser, com um s (como muitos trilhões). Então você pode escolher um s 'dizer cerca de 1.000.000, multiplicar todos os números envolvidos por (s' / s), encontrar itens com uma soma perto de 1.000.000 e, em seguida, escolha os itens originais. Tente por algumas somas próximas de 1.000.000.

Answer 3

Graças ao comentário @Yuval Eu fui levado ao problema da mochila que é exatamente o que eu estava procurando.

Embora eu não tenha entendido grande parte das soluções propostas a este problema NP-completo na Wikipedia, pensei em uma abordagem rápida, mas totalmente não confiável:

Simplifique a lista de inteiros disponíveis do menor para o maior e comece a adicioná-los até que a condição desejada seja atendida.

Eu acho que se todas as diferenças entre dois membros do conjunto inteiro não variam muito, essa abordagem provavelmente vai dar a melhor e única solução.