Implementa el algoritmo que resuelve el problema de la mochila : Disponemos de n
objetos y una mochila de capacidad M de forma que si una fracción xi de un objeto i es
introducida en la mochila se obtiene un beneficio xibi. El objetivo consiste en llenar la mochila maximizando el beneficio
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#include "math.h"
const int n=8; //Longitud de los pesos
const int capacidad=15; //Capacidad de la Mochila
//******************************************
// Imprime matriz estatica n x n
//******************************************
void printmat(int m[][capacidad+1],int f, int c){
int i,j;
for(i=0;i<f;i++){
for(j=0;j<c;j++){
printf("%d ",m[j]);
}
printf("\n");
}
}//fin printmat
//******************************************
// Imprime matriz lineal n
//******************************************
void printmatl(int m[],int c){
int j;
for(j=0;j<c;j++){
printf("%d ",m[j]);
}
printf("\n");
}//fin printmat
//******************************************
// Imprime matriz en base a punteros
//******************************************
void printptr(int *a,int f, int c){
int i,j;
for(i=0;i<f;i++){
for(j=0;j<c;j++){
printf("%d ",*a);
//cout<<*a;
a++;
}
printf("\n");
}
}//fin printmat
//*******************************************************
// Genera valores aleatorios con punteros para la matriz
//*******************************************************
void genera_mat(int *a,int c){
int j;
for(j=0;j<c;j++){
*a=rand()%10;
//printf("%d ",*a);
a++;
}
}//fin genera_mat
//*******************************************
// Genera valores aleatorios para la matriz
//*******************************************
void genera_mat_e(int a[],int c){
int j;
for(j=0;j<c;j++){
a[j]=rand()%10;
//printf("%d ",*a);
}
}//fin genera_mat
//*******************************************
// Genera valores aleatorios para la matriz
//*******************************************
void genera_mat_0(int a[][capacidad+1],int n){
int i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
a[j]=0;
//printf("%d ",*a);
}
}
}//fin genera_mat
//**********************************
// Funcion Mochila
//**********************************
void Mochila(int matriz_mochila[][capacidad+1],int pesos[], int beneficios[], int capacidad, int n){
int i,j,c;
// Rellenamos la 1ra fila de ceros
for(i=0;i<=capacidad;i++){
matriz_mochila[0]=0;
}
// Rellenamos la 1ra columna de ceros
for(i=0;i<=n;i++){
matriz_mochila
=0;
}
for(j=1;j<=n;j++){
for(c=1;c<=capacidad;c++){
if(c<pesos[j-1]){
matriz_mochila[j][c]=matriz_mochila[j-1][c];
}
else{
if(matriz_mochila[j-1][c]>matriz_mochila[j-1][c-pesos[j-1]]+beneficios[j-1]){
matriz_mochila[j][c]=matriz_mochila[j-1][c];
}
else{
matriz_mochila[j][c]=matriz_mochila[j-1][c-pesos[j-1]]+beneficios[j-1];
}
}
}//fin for c
}//fin for i
}//fin Mochila
int Menu()
{
char resp[20];
do {
system("cls");
printf("---------------------------------\n\n");
printf(" MENU PRINCIPAL \n");
printf(" ALGORITMO DE LAS MOCHILAS \n");
printf("----------------------------------\n\n");
printf("1- Ingrese Nro de filas y columnas de las matrices\n");
printf("2- Generar Valores Aletorios para Pesos y Beneficios\n");
printf("3- Mostrar Valores de las Matrices Pesos y Beneficios\n");
printf("4- Resolver Algoritmo de las Mochilas\n");
printf("5- Mostrar Resultado\n");
printf("0- Salir\n");
fgets(resp, 20, stdin);
} while(resp[0] < '0' && resp[0] > '5');
return resp[0];
}
//*******************
//
// Programa principal
//
//********************
void main(){
int pesos[n]={0};
int beneficios[n]={0};
int mochi[n+1][capacidad+1];
int (*mpesos)=pesos;
int (*mbeneficios)=beneficios;
int (*pmochi)=mochi[n];
int opcion;
do {
opcion = Menu();
switch(opcion) {
case '1': // Filas y Columnas
printf("Por restricciones del Lenguaje de Programacion\n");
getch();
break;
case '2': // Genera valores
genera_mat_e(mpesos,n);
genera_mat_e(mbeneficios,n);
printf("Matrices de Pesos y Beneficios generadas");
getch();
break;
case '3': // Imprime matrices
printf("Matriz de Pesos\n");
printmatl(pesos,n);
printf("\n");
printf("Matriz de Beneficios\n");
printmatl(beneficios,n);
printf("\n");
getch();
break;
case '4': // Resuelve Problemas
genera_mat_0(mochi,n);
Mochila(mochi,pesos, beneficios, capacidad, n);
printf("Operacion Terminada");
getch();
break;
case '5': // Mostrar Resultado
printf("Matriz de Pesos\n");
printmatl(pesos,n);
printf("Matriz de Beneficios\n");
printmatl(beneficios,n);
printf("Matriz Resultado\n");
printmat(mochi,n,capacidad);
getch();
break;
}
} while(opcion != '0');
}//fin main
komo ordeno esto para que me vaya????? gracias!!
Mostrar Mensajes