0

Problema da Mochila: Vamos resolver esse desafio?

#Python
Monique Melo
Monique Melo

Como maximizar o valor com um peso máximo? E como de costume, segue as dicas de conhecimentos prévios que vão te ajudar a entender melhor a resolução desse desafio: laços de repetiçãocondiçõesfunçõesdicionários.


[Contexto do Problema]

O problema da mochila tem mais de 40 anos, exposto por Richard Karp (matemático e cientista americano) e trata-se de um problema de combinatória. Existem algumas variações e especificidades desse problema, porém trarei aqui a forma mais simples desse desafio com regras interessantes a serem vencidas.

Sem mais delongas, vamos as regras do desafio:

Imagine um lugar que você sempre quis muito conhecer e depois de ganhar uma bagatela na loteria você finalmente poderá realizar esse sonho e fazer sua viagem.

Para tal, você precisa levar alguns itens importantes em sua mochila, no entanto, ela tem limite de peso e isso pode ser um problema para você que precisa muito priorizar esses itens valiosos. Então, para decidir quais itens levar, você escreveu em seu caderno o valor de cada item e também pesou cada um deles. Como você andou praticando bastante Python a fim de tentar criar ̶b̶o̶t̶s̶ ̶p̶a̶r̶a̶ ̶v̶o̶t̶a̶r̶e̶m̶ ̶p̶a̶r̶a̶ ̶v̶o̶c̶ê̶ ̶n̶o̶ ̶B̶B̶B̶, você resolveu criar um programinha que resolverá o seu problema atual.

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.

Agora vamos aos critérios de escolha:

  • Para definir qual item será analisado primeiro, você deve escolher, entre os itens disponíveis aquele com a maior razão de valor sobre o peso. Em caso de empate, o item com o menor peso deve ser o escolhido.
  • A regra acima é válida até que não seja possível colocar mais nenhum item na mochila.

[Exemplo]

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: Fone de OuvidoLivro de Python e Garrafa de água.
  • Ao analisarmos a maior razão encontramos um empate entre o Fone de Ouvido e o Livro de Python, como o Fone de Ouvido tem menor peso, ele foi escolhido antes do livro. Nesse ponto, a mochila está pesando 2400g (2000g + 400g).
  • Note que, o próximo item de maior razão é o Notebook, porém ele não foi escolhido, pois nesse momento ele não cabia na mochila.
  • A Garrafa de água que é a próxima cabe em nossa mochila, deixando ela com 3000g. Ou seja, tivemos nesse exemplo, um aproveitamento de 100% da nossa mochila.

[Entrada de Dados]

O seu programa irá receber dois inteiros I e C, um em cada linha, representando o número de itens e a capacidade da mochila, respectivamente. Em seguida o programa receberá I linhas com números inteiros representando os pesos dos itens e I linhas com números inteiros representando os valores dos itens. Os itens estarão ordenados pelo peso.

[Saída de Dados]

A saída deve informar dois números inteiros (um por linha): um com a soma dos valores correspondentes aos objetos colocados na mochila e outro com a soma dos pesos dos objetos colocados na mochila.

Acesse esse link para ter acesso a vários casos de teste para testar a resolutividade do seu código. Você pode abrir com sua IDE, bloco de notas, entre outros.: https://www.dropbox.com/s/b0w8prn7r678jzj/casos%20de%20teste.zip?dl=0

Tendo dito todas as regras, tá na hora de colocar a mão na massa. Te convido para realmente tentar resolver esse desafio antes mesmo de checar a minha solução abaixo. Mãos à obra então?

[Solução]

Antes de te mostrar a solução, é importante ressaltar que essa resolução é apenas uma das milhares formas que você pode resolver. Inclusive, só deixar no comentário para que todos possamos aprender. Eu resolvi dessa forma, pois foi a que mais gostei e por ter elementos interessantes de serem absorvidos. Toda solução é boa quando resolve nosso problema, a optimização vem com o tempo :)

Agora vamos a solução!!!

Bom, eu iniciei a resolução pela linha 17 definindo as entradas de dados exigidas pelo problema. Depois criei os dois primeiros for para recebermos as outras entradas e atribuí cada uma delas a um dicionário com chaves representando o valor, o peso e a razão. E por fim, adicionei esse dicionário na nossa lista chamada mochila.

Já no for abaixo (linha 28), era necessário percorrer a nossa mochila e passar no parâmetro key a função criada nas linhas iniciais. Essa função, como o próprio nome diz, foi criada para definir as regras da nossa ORDENAÇÃO visto que ela considera primeiro a razão, mas em caso de empate ela deve optar pelo menor peso.

Na linha 29, nós criamos uma condição para checar se a nossa mochila não tem mais capacidade, caso não tenha, o programa deve parar.

Na linha 31, testamos através do if se a capacidade da mochila é maior ou igual ao peso que estamos inserindo na mochila, pois se for true, a partir da linha 32, diminuí a capacidade da mochila para o peso inserido nela. Aumentei o peso total conforme os itens adicionados na mochila e também aumentei o valor total conforme os valores dos itens inseridos na mochila. Já na linha 36, apenas imprimimos o que foi solicitado.


Espero ter ajudado com esse simples desafio os que estão praticando esses conceitos na programação. Qualquer dúvida, só colocar nos comentários que eu respondo.

0
8

Comentários (0)

Apaixonada por tecnologia, jogos e board games. 🖥 🎲

Brasil