Solução Em Busca do Corpo Perfeito

0 Flares Facebook 0 0 Flares ×

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:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: