Ir para conteúdo
Fórum Script Brasil
  • 0

Versão do problema da mochila


Carolina Esther

Pergunta

Gente, preciso de uma ajuda enorme com um problema aqui... 

 

 

Por alguma razão você teve que passar o último ano sem poder viajar. Agora finalmente é hora de planejar a próxima viagem, está quase tudo pronto, falta apenas decidir o que você vai levar na sua mochila.

Você separou vários itens que podem ser úteis na viagem, mas a sua mochila tem um limite de peso. Para decidir quais itens levar, você atribuiu um valor para cada item, dependendo do quão útil ele será na viagem. Seu objetivo agora é escolher os itens de forma que a soma dos valores seja elevada, mas que a soma dos pesos não ultrapasse a capacidade da mochila.

Pesquisando sobre esse problema você descobre que ele é uma versão do Problema da Mochila e que existe uma regra razoavelmente simples que te dará um resultado satisfatório. Essa regra consiste em escolher, entre os itens disponíveis que cabem na mochila, aquele com a maior razão de valor sobre o peso. Em caso de empate, o item com o menor peso deve ser escolhido. Os itens devem ser escolhidos por essa regra até que não seja possível colocar mais nenhum item na mochila.

O exemplo a seguir mostra as escolhas entre um conjunto de cinco itens considerando uma mochila com capacidade de 3000g:

 

 

 

 

Nesse exemplo os itens foram escolhidos na seguinte ordem: guarda-chuva, livro e garrafa de água. O guarda-chuva foi escolhido antes do livro, pois o peso dele é menor. Note que, o notebook não foi escolhido após o livro, pois nesse momento ele não cabia na mochila. Da mesma forma a jaqueta não pode ser inserida após a garrafa de água.

 

image.thumb.png.9cf1fd190a4c31163eae50ee09a7e631.png

 

 

Segue o exemplo:

 

image.thumb.png.0fc09cce2df06170b50f7066f3665a35.png

Link para o comentário
Compartilhar em outros sites

0 respostass a esta questão

Posts Recomendados

Até agora não há respostas para essa pergunta

Participe da discussão

Você pode postar agora e se registrar depois. Se você já tem uma conta, acesse agora para postar com sua conta.

Visitante
Responder esta pergunta...

×   Você colou conteúdo com formatação.   Remover formatação

  Apenas 75 emoticons são permitidos.

×   Seu link foi incorporado automaticamente.   Exibir como um link em vez disso

×   Seu conteúdo anterior foi restaurado.   Limpar Editor

×   Você não pode colar imagens diretamente. Carregar ou inserir imagens do URL.



  • Estatísticas dos Fóruns

    • Tópicos
      152,3k
    • Posts
      652,4k
×
×
  • Criar Novo...