Actividad06_Martinez_Nava_Jorge_Justino - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

Universidad de Guadalajara 
 
Centro Universitario de Ciencias Exactas e Ingeniería 
 
Algoritmia 
 
Profesor: Salomón Eduardo Ibarra Chávez 
 
Alumno: Jorge Justino Martinez Nava 
 
Actividad 06 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1. Suponga que tiene una lista de objetos con diferentes pesos en 
kilogramos y valores en pesos [peso,valor]. Usted tiene una 
mochila que puede cargar un pedo máximo de X kilogramos. 
Diselar un algoritmo voraz que elija los objetos de la lista que 
maximicen el valor de los objetos que se llevarán en la mochila. 
([87, 33], [45, 12], [20, 16], [54, 23], [45, 42], [26, 12], [30, 13], [54, 
21], [76, 47], [12, 22], [64,44], [23, 11]) 
 
mochila(m:entero,v[n]:entero,w[n]:entero,x[n]:entero); 
Para i=1 hasta n hacer 
x[i]=0; 
peso=0; 
Mientras peso < m hacer 
j=mejor objeto restante; 
Si peso + w[i] <= m hacer 
x[i]=1 
peso=peso + w[i]; 
Fin si 
Sino hacer 
x[i]=(m - peso)/w[i]; 
peso=m; 
Fin sino 
Fin para 
 
 
 
 
 
 
 
 
2. Dado un sistema monetario S de longitud K y una cantidad de 
cambio C, devolver una solución (si existe) que nos indique el 
número de monedas de S equivalente a C, es decir, que nos 
muestre el cambio para C a partir de monedas de S. 
 
Cambio(m[n]:entero,entero e) 
cont : entero; 
i : entero; 
mientras e!=0 hacer 
cont += e/m[i]; 
e = e % m[i]; 
i++; 
Fin mientras