Solução Em Busca do Corpo Perfeito

knapsack.cpp

#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;
}