elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Rompecabezas de Bitcoin, Medio millón USD en premios


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  problema de la mochila en c!!
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: problema de la mochila en c!!  (Leído 11,375 veces)
Janfry

Desconectado Desconectado

Mensajes: 7


Ver Perfil
problema de la mochila en c!!
« en: 8 Diciembre 2010, 16:06 pm »

lo necesito kon urgencia, si lo teneis me lo pasais aki, muchisimas gracias!


En línea

pitka

Desconectado Desconectado

Mensajes: 25



Ver Perfil
Re: problema de la mochila en c!!
« Respuesta #1 en: 8 Diciembre 2010, 16:35 pm »

Según leí en las reglas aquí no se hacen las tareas si no muestras algo de código que hayas hecho y ahí si los que saben te orientan, yo la verdad estoy muy verde en programación y lamento no poder ayudarte con mis conocimientos, pero me imagino que algo así es lo que buscas



http://espanol.answers.yahoo.com/question/index?qid=20100623063532AAhoOsj
   :-X


En línea

Janfry

Desconectado Desconectado

Mensajes: 7


Ver Perfil
Re: problema de la mochila en c!!
« Respuesta #2 en: 8 Diciembre 2010, 17:19 pm »

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!!
En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: problema de la mochila en c!!
« Respuesta #3 en: 8 Diciembre 2010, 17:43 pm »

Del problema de la mochila hay muchas variaciones y según entiendo de lo que dices, tú estás buscando resolver lo que se conoce como Fractional Knapsack Problem, mientras que el código que has puesto a simple vista parece que hace una DP para resolver el problema de la mochila estándar, donde los objetos no se pueden fraccionar (o se meten o no se meten).

En tu caso, el problema del Fractional Knapsack Problem, es mucho más simple y no requiere programación dinámica. Lo puedes resolver con un greedy muy tonto, ordenando lo objetos según beneficio/tamaño e ir cogiendo en orden los que tengan mayor cociente hasta llenar la mochila.
En línea

Littlehorse
All the world's a stage
Moderador
***
Desconectado Desconectado

Mensajes: 2.714


Nie Dam Sie


Ver Perfil WWW
Re: problema de la mochila en c!!
« Respuesta #4 en: 8 Diciembre 2010, 17:55 pm »

Citar
lo necesito kon urgencia, si lo teneis me lo pasais aki, muchisimas gracias!

Janfry, aquí urgente no es nada. Si tienes que resolver una tarea, lo que tienes que hacer con urgencia es estudiar.

Citar
komo ordeno esto para que me vaya????? gracias!!

En esta sección no se hacen tareas. Lee las reglas.
Puedes comenzar por aqui para poder aprender los conceptos básicos implicados, y cuando tengas una duda puntual, realizas un hilo.

Saludos
En línea

An expert is a man who has made all the mistakes which can be made, in a very narrow field.
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
mochila HASP
Ingeniería Inversa
Juanbayne 0 2,018 Último mensaje 3 Enero 2005, 04:34 am
por Juanbayne
mochila
Ingeniería Inversa
pedrico 4 5,320 Último mensaje 21 Julio 2006, 11:46 am
por Eraser
Problema de mochila hardlock
Ingeniería Inversa
diantred 0 1,358 Último mensaje 2 Octubre 2012, 06:41 am
por diantred
Problema con mochila (dongle o llave)
Seguridad
diantred 0 1,837 Último mensaje 12 Octubre 2012, 05:49 am
por diantred
Problema de la mochila (binaria)
Programación General
jca1 4 950 Último mensaje 3 Septiembre 2019, 19:18 pm
por WHK
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines