Solução por Rogério Júnior
Infelizmente, um algoritmo guloso que sempre come o pedaço com maior valor proteico ou com maior percentual de proteína acaba errando. O problema é uma adaptação de um clássico algoritmo chamado knapsack. É muito importante entendê-lo e saber implementá-lo antes de fazer qualquer competição de programação. Se você não o conhece, clique aqui para ver a aula do Curso Noic de Informática sobre Programação Dinâmica. A abordagem estilo top-down, que acaba sendo mais rápida neste caso, usa uma função recursiva que verifica, para cada objeto, se devemos colocá-lo ou não na mochila, ou no caso, se devemos comer ou não o pedaço de carne. A implementação é muito simples e usa uma função que já retorna o máximo de proteína que nosso físico pode comer, que chamaremos $$knapsack$$. Ela receberá como parâmetros o $$int$$ $$pedaco$$, que será o pedaço de carne que vamos analisar se comeremos ou não e o $$int$$ $$espaco$$ que representa quanto espaço ainda há na barriga de Kakariús, ou seja, quantos gramas de carne ele ainda pode comer. A solução é melhor explicada direto no comentário do código:
https://gist.github.com/rogerioagjr/25509ba10b7977701d43
Deixe um comentário