[Python Challenger] Problema da Mochila: Vamos resolver esse desafio?

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ção, condições, funções, dicioná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 Ouvido, Livro 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.

Se gostou desse post, não esquece de compartilhar com os amigos e curtir aqui.