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 
. Ela receberá como parâmetros o 
, que será o pedaço de carne que vamos analisar se comeremos ou não e o 
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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> // printf e scanf | |
| #include <cstring> // memset | |
| #define MAX 2200 // limite de N e P | |
| int max(int a, int b){ // função max, usada no knapsack, retorna o maior dentre dois números | |
| if(a>b) return a; | |
| return b; | |
| } | |
| int n, p, peso[MAX], prot[MAX]; // declaração de variáveis | |
| int tab[MAX][MAX]; // tabela de pd | |
| int knapsack(int pedaco, int espaco){ // função do knapsack recebe o pedaço que vou analisar (pedaco) e quanto ainda posso comer (espaco) | |
| if(tab[pedaco][espaco]>=0) return tab[pedaco][espaco]; // se já calculei o valor da função para esses parâmetros, retorn ele | |
| if(pedaco>n) return tab[pedaco][espaco]=0; // se já analisei todos os pedaços, retorn 0 | |
| int come; // o quanto ganho se comer o pedaço | |
| // se poder comê-lo, ganho seu valor, mais o melhor entre comer ou não o próximo | |
| if(peso[pedaco]<=espaco) come=prot[pedaco]+knapsack(pedaco+1, espaco-peso[pedaco]); | |
| else come=0; // se não tiver mais espaço para comê-lo, faça a variável come receber zero | |
| int nao_come=knapsack(pedaco+1, espaco); // não comer o pedaço me dará apenas o melhor entre comer ou não o próximo | |
| return tab[pedaco][espaco]=max(come, nao_come); // devo retornar o melhor entre comer ou não o pedaço | |
| } | |
| int main(){ | |
| scanf("%d %d", &p, &n); // leio o valor de P e N | |
| memset(tab, -1, sizeof(tab)); // marco todos os valores da tabela como "não calculados" | |
| for(int i=1; i<=n; i++) scanf("%d %d", &peso[i], &prot[i]); // leio o peso e valor de cada pedaço | |
| printf("%d\n", knapsack(1, p)); // imprimo o valor de knapsack começando do objeto 1 e com todo o espaço que Kakariús aguenta | |
| return 0; | |
| } |