Um algoritmo de embalagem ... tipo de

Question

Dada uma série de itens, cada um dos quais tem um value e cost, o que é o melhor algoritmo determinar os itens necessários para chegar a um valor mínimo com o mínimo custo por exemplo:?

Item: Value -> Cost
-------------------
A     20   -> 11
B     7    -> 5
C     1    -> 2

MinValue = 30
naive solution: A + B + C + C + C. Value: 30, Cost 22
best option: A + B + B.            Value: 34, Cost 21

Note que o valor global:. Relação custo no final é irrelevante (A + A iria dar-lhe o melhor valor para o dinheiro, mas A + B + B é uma opção mais barata que atinge o valor mínimo)

Answer 1

Este é o problema da mochila. (Isto é, a versão decisão deste problema é o mesmo que a versão decisão do problema da mochila, embora a versão otimização do problema da mochila é geralmente indicado de forma diferente.) É NP-hard (o que significa que nenhum algoritmo é conhecido que é polinomial no "tamanho" - número de bits - na entrada). Mas se seus números são pequenos (o maior "valor" na entrada, dizer, os custos não importam)., Então não é uma solução de programação dinâmica simples

Vamos melhor [v] ser o custo mínimo para obter um valor de (exatamente) v Depois, você pode calcular os valores melhores [] para que todos v, por (inicializar tudo melhor [v] ao infinito e):.

best[0] = 0
best[v] = min_(items i){cost[i] + best[v-value[i]]}

Então olha para melhor [v] para valores upto o mínimo que você deseja, mais o maior valor; o menor dos que lhe dará o custo.

Se você deseja que os itens reais (e não apenas o custo mínimo), você pode manter alguns dados extras, ou apenas olhar através da série de melhor [] s e inferir a partir dele.

Answer 2

Este problema é conhecido como programação linear inteira. É NP-hard. No entanto, para pequenos problemas como o seu exemplo, é trivial para fazer uma rápida poucas linhas de código à força simplesmente bruta todas as baixas combinações de opções de compra.

NP-harddoesn't impossível média ou mesmo caro, significa que o problema torna-se rapidamente mais lento para resolver os problemas de maior escala. No seu caso, com apenas três itens, você pode resolver isso em meros microssegundos.

Para a pergunta exata do que é o melhor algoritmo em geral .. existem livros inteiros sobre ele. Um bom começo é bom e velho Wikipedia.

Answer 3

Editar Esta resposta é redigido por conta de ser factualmente incorreto. Seguindo o conselho neste só irá causar-lhe mal.

Esta não é realmente o problema da mochila, porque ele assume que você não pode embalar mais itens do que há espaço para em algum recipiente. Em você caso você queira encontrar a combinação mais barata que irá preencher o espaço, permitindo o fato de que estouro pode ocorrer.

A minha solução, que eu não sei é o ideal, mas deve ser bastante estreita, seria para calcular para cada item da relação custo-benefício, encontrar o item com maior custo-benefício e preencher a estrutura com este item até não há espaço para mais um item. Então eu iria testar para ver se havia uma combinação com qualquer um dos outros itens disponíveis que poderiam preencher o slot disponível para menos que o custo de um dos itens mais baratos e, em seguida, se essa solução a existir, use essa combinação de outra forma usar um mais dos itens mais baratos.

Amenddum Isto pode realmente ser também NP-completo, mas tenho certeza que ainda não sou. De qualquer forma para todos os efeitos práticos, esta variação deve ser muito mais rápido do que a solução ingênua.