Jimenez Sanchez Reporte Alg Mochila

CU VALLES



Alumno: Valente Joel Jiménez Sánchez
Código: 209208461
Profesor: Ricardo Magallanes
Materia: análisis de algoritmos y computabilidad.
Mecatrónica


"Reporte de práctica del algoritmode la mochila (ávido)"

Objetivo de la práctica.
Calcular el algoritmo mediante su complejidad, para ello utilizaremos el procedimiento que hemos venido haciendo en el curso.
Materiales:
ComputadoraSoftware Dev c++


Teoría básica
Un algoritmo voraz (también conocido como ávido, devorador o goloso) es aquel que, para resolver un determinado problema, sigue una heurística consistente en elegir laopción óptima en cada paso local con la esperanza de llegar a una solución general óptima. Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar sufuncionamiento. Normalmente se aplica a los problemas de optimización.








Algoritmo.
Ingresar cantidad de objetos.
Ingresar el peso y el costo de cada objeto.
Ingresar la capacidad de la mochila.Procesar la información con el algoritmo ávido.
Diagrama de flujo














Calculo de la complejidad.
El espacio del algoritmo anterior también es de Θ(n 3 ) I se puede mejorar el espacio para estecálculo teniendo en cuenta: I cada D[i,j,k] sólo necesita conocer los valores en D[∗,∗,k −1]. Esto reduce el espacio a Θ(n 2 ) I para todo k, D[k,j,k] = D[k,j,k −1] y D[i,k,k] = D[i,k,k −1]. Esto reduceel espacio a Θ(1) (sin contar el necesario para almacenar el resultado) I el resultado es de O(n 2 )





Programa en texto
#include
#include
#include
using namespacestd;

void Mochila(int n, int Peso[], int Valor[], int PMax){
int *a = new int[PMax];
int *temp = new int[PMax];
int aux;

for (int i = 0; i <= PMax; i++){
a[i] = 0;temp[i] = -1;
}


a[0] = 0;
for (int i = 1; i <= PMax; i++)
for (int j = 0; j < n; j++)
if ((Peso[j] <= i) && (a[i] < a[i - Peso[j]] + Valor[j])){...

Leer documento completo

Regístrate para leer el documento completo.