Autor
|
Tema: problema de la mochila en c!! (Leído 14,897 veces)
|
Janfry
Desconectado
Mensajes: 7
|
lo necesito kon urgencia, si lo teneis me lo pasais aki, muchisimas gracias!
|
|
|
En línea
|
|
|
|
|
Janfry
Desconectado
Mensajes: 7
|
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
Mensajes: 1.900
|
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
Mensajes: 2.714
Nie Dam Sie
|
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. 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.
|
|
|
|
Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
mochila
Ingeniería Inversa
|
pedrico
|
4
|
6,771
|
21 Julio 2006, 11:46 am
por Eraser
|
|
|
Problema de mochila hardlock
Ingeniería Inversa
|
diantred
|
0
|
2,367
|
2 Octubre 2012, 06:41 am
por diantred
|
|
|
Problema con mochila (dongle o llave)
Seguridad
|
diantred
|
0
|
3,152
|
12 Octubre 2012, 05:49 am
por diantred
|
|
|
Problema de la mochila (binaria)
Programación General
|
jca1
|
4
|
3,460
|
3 Septiembre 2019, 19:18 pm
por WHK
|
|
|
Problema de la mochila
Programación General
|
jca1
|
5
|
5,420
|
22 Enero 2022, 00:16 am
por jca1
|
|