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 doProblema da Mochilae 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.
Pergunta
Carolina Esther
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.
Segue o exemplo:
Link para o comentário
Compartilhar em outros sites
0 respostass a esta questão
Posts Recomendados
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.