Created
December 24, 2018 22:36
-
-
Save Germanblandin1/f133e3b810722ae7bc41d1aa13f6ceb2 to your computer and use it in GitHub Desktop.
Reto 8 - Diciembre 23 de Platzi
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
EL programa se realizo en lenguaje C++, en teoria funciona con cualquier compilador de c++ sin embargo yo lo realize usando un compilador de g++ incluido en cygwin | |
El algoritmo usa la tecnica de programacion dinamica que es uno de los algoritmos mas eficientes para resolver el problema de la mochila. | |
Esta tecnica tiene una complejidad de O(N*W) donde N es la cantidad de cajas y W el peso maximo que podria tener la bolsa. | |
Otra tecnica que se puede emplear es Backtraking sin embargo esta tecnica es bastante ineficiente, pero como ventaja gasta menos que usando Programacion dinamica. | |
El programa debe contener el archivo entrada.in para su funcionamiento. | |
El archivo se estructura de la siguiente manera: | |
N W | |
Nombre1 Valor1 Peso1 | |
Nombre2 Valor2 Peso2 | |
Nombre3 Valor3 Peso3 | |
... | |
NombreN ValorN PesoN | |
Donde N son la cantidad de cajas, W es el peso maximo que la bolsa puede llevar, y las siguientes N lineas corresponden con los nombres,valores y pesos de cada caja respectivamente. |
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
5 150 | |
A 100 40 | |
B 20 10 | |
C 40 120 | |
D 20 20 | |
E 10 10 |
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
//creado por German Blandin. Email: Germanblandin18@gmail.com | |
#include<iostream> | |
#include<stdio.h> | |
#define INF 0x3f3f3f3f | |
#define MAXPESO 10000 | |
int resul[100][MAXPESO]; //matriz para guardar los resultados del DP | |
bool memo[100][MAXPESO]; //matriz que se usa para marcar las soluciones ya obtenidas | |
int seleccion[100][MAXPESO]; //matriz para ver que solucion tomo y luego imprimir la solucion | |
int pesos[100]; //arreglo que guarda los pesos de las cajas0 | |
int valor[100]; //arreglo que guarda el valor de las cajas | |
char nombre[100]; //arreglo qie guarda el nombre de cada caja | |
int n; //cantidad de cajas | |
int limite; //limite maximo de la bolsa del grinch | |
//algoritmo recursivo de programacion dinamica para resolver el problema de la mochila (Knapsack problem) | |
//Tenemos el indice (i) de las cajas, y el peso que vamos llevando mientras el algoritmo ejecuta | |
//Arroja el valor de la solucion optima | |
int dp(int i,int peso){ | |
if(peso>limite) return -INF; | |
if(i>=n) return 0; | |
int &mejor=resul[i][peso]; | |
if(memo[i][peso]) return mejor; | |
memo[i][peso]=true; | |
int sol1=dp(i+1,peso); | |
int sol2=dp(i+1,peso+pesos[i])+valor[i]; | |
if(sol1>sol2){ | |
mejor=sol1; | |
seleccion[i][peso]=0; | |
}else{ | |
mejor=sol2; | |
seleccion[i][peso]=1; | |
} | |
return mejor; | |
} | |
//inicializa las estructuras de datos para ejecutar el algoritmo | |
void inicializar(){ | |
for(int i=0;i<n;i++){ | |
for(int j=0;j<MAXPESO;j++){ | |
memo[i][j]=false; | |
resul[i][j]=-INF; | |
seleccion[i][j]=-1; | |
} | |
} | |
} | |
//imprime la combinacion de cajas optima | |
void imprimirSolucion(int i,int peso){ | |
if(i>=n) return; | |
if(seleccion[i][peso]==0){ | |
imprimirSolucion(i+1,peso); | |
}else{ | |
printf("%c y su peso %d\n",nombre[i],pesos[i]); | |
imprimirSolucion(i+1,peso+pesos[i]); | |
} | |
} | |
//Lee el archivo de entrada | |
bool leerArchivo(){ | |
FILE* entrada; | |
char letra[10]; | |
entrada=fopen("entrada.in","r"); | |
if(entrada!=NULL){ | |
fscanf(entrada,"%d %d",&n,&limite); | |
for(int i=0;i<n;i++){ | |
fscanf(entrada,"%s %d %d",letra,&valor[i],&pesos[i]); | |
nombre[i]=letra[0]; | |
} | |
fclose(entrada); | |
return true; | |
} | |
printf("No se pudo abrir el archivo\n"); | |
return false; | |
} | |
//funcion principal | |
int main(){ | |
if(leerArchivo()){ | |
inicializar(); | |
printf("La combinacion optima tiene un valor de: %d y la combinacion es: \n",dp(0,0)); | |
imprimirSolucion(0,0); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment