Skip to content

Instantly share code, notes, and snippets.

@Germanblandin1
Created December 24, 2018 22:36
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Germanblandin1/f133e3b810722ae7bc41d1aa13f6ceb2 to your computer and use it in GitHub Desktop.
Save Germanblandin1/f133e3b810722ae7bc41d1aa13f6ceb2 to your computer and use it in GitHub Desktop.
Reto 8 - Diciembre 23 de Platzi
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.
5 150
A 100 40
B 20 10
C 40 120
D 20 20
E 10 10
//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