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: