Last active
August 29, 2015 14:19
-
-
Save rogerioagjr/25509ba10b7977701d43 to your computer and use it in GitHub Desktop.
Solução Em Busca do Corpo Perfeito
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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment