fork download
copy 
  1. #include <ctype.h>
  2. #include <unistd.h>
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <sys/time.h>
  6. #include <math.h>
  7. #include <stdbool.h>
  8.  
  9. // Définition des structures nécessaires
  10. typedef struct IP_problem {
  11.     int nv; // Nombre de variables
  12.     int nc; // Nombre de contraintes
  13.     double *x; // Solution
  14.     double *cost; // Coûts
  15.     char *c_type; // Type des variables
  16.     double *up_bound; // Bornes supérieures
  17.     double *low_bound; // Bornes inférieures
  18.     char **var_name; // Noms des variables
  19.     double *rhs; // Partie droite des contraintes
  20.     char *sense; // Sens des contraintes
  21.     int *rmatbeg; // Début des contraintes
  22.     int *rmatind; // Indices des contraintes
  23.     double *rmatval; // Valeurs des contraintes
  24.     int nz; // Nombre de non-zéros
  25.     char **const_name; // Noms des contraintes
  26.     int solstat; // Statut de la solution
  27.     double objval; // Valeur de l'objectif
  28. } IP_problem;
  29.  
  30. typedef struct dataSet {
  31.     int n; // Nombre d'objets
  32.     int b; // Capacité
  33.     int g; // Capacité secondaire
  34.     int *c; // Valeurs des objets
  35.     int *a; // Poids des objets
  36.     int *f; // Poids secondaires des objets
  37.     IP_problem master; // Problème maître
  38. } dataSet;
  39.  
  40. // Fonction pour obtenir le temps actuel
  41. double getTime() {
  42.     struct timeval tv;
  43.     gettimeofday(&tv, NULL);
  44.     return tv.tv_sec + tv.tv_usec * 1e-6;
  45. }
  46.  
  47. // Fonction de résolution avec CPLEX (simulation ici)
  48. void solve_1DKP(dataSet *data) {
  49.     // Simulation d'une solution optimale
  50.     data->master.objval = 100.0; // Exemple de valeur optimale
  51. }
  52.  
  53. // Fonction de programmation dynamique pour le 1DKP
  54. int dynamicProgramming1DKP(int capacity, int *weights, int *values, int n) {
  55.     int i, w;
  56.     int **dp = (int **)malloc((n + 1) * sizeof(int *));
  57.     for (i = 0; i <= n; i++) {
  58.         dp[i] = (int *)malloc((capacity + 1) * sizeof(int));
  59.     }
  60.  
  61.     // Initialisation
  62.     for (i = 0; i <= n; i++) {
  63.         for (w = 0; w <= capacity; w++) {
  64.             if (i == 0 || w == 0) {
  65.                 dp[i][w] = 0;
  66.             } else if (weights[i - 1] <= w) {
  67.                 dp[i][w] = fmax(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
  68.             } else {
  69.                 dp[i][w] = dp[i - 1][w];
  70.             }
  71.         }
  72.     }
  73.  
  74.     int result = dp[n][capacity];
  75.  
  76.     // Libération de la mémoire
  77.     for (i = 0; i <= n; i++) {
  78.         free(dp[i]);
  79.     }
  80.     free(dp);
  81.  
  82.     return result;
  83. }
  84.  
  85. int main(int argc, char **argv) {
  86.     int rval = 0;
  87.     char c;
  88.     char instance_file[1024];
  89.     snprintf(instance_file, 1024, "%s", "instance3.csv");
  90.  
  91.     while ((c = getopt(argc, argv, "F:h")) != EOF) {
  92.         switch (c) {
  93.             case 'F':
  94.                 snprintf(instance_file, 1024, "%s", optarg);
  95.                 break;
  96.  
  97.             case 'h':
  98.                 fprintf(stderr, "Usage: ./TP2 [options]\nOptions:\n\n");
  99.                 fprintf(stderr, "******** INSTANCE DATA ********\n");
  100.                 fprintf(stderr, "\t-F Instance file name to load............................(default %s).\n", instance_file);
  101.                 break;
  102.             default:
  103.                 exit(0);
  104.         }
  105.     }
  106.  
  107.     // Initialisation des données
  108.     dataSet data;
  109.     data.n = 5; // Exemple : 5 objets
  110.     data.b = 10; // Capacité du sac
  111.     data.c = (int *)malloc(data.n * sizeof(int));
  112.     data.a = (int *)malloc(data.n * sizeof(int));
  113.     data.f = (int *)malloc(data.n * sizeof(int));
  114.  
  115.     // Exemple de valeurs et poids
  116.     data.c[0] = 10; data.a[0] = 2;
  117.     data.c[1] = 20; data.a[1] = 3;
  118.     data.c[2] = 30; data.a[2] = 4;
  119.     data.c[3] = 40; data.a[3] = 5;
  120.     data.c[4] = 50; data.a[4] = 9;
  121.  
  122.     double start, end;
  123.  
  124.     // Résolution avec CPLEX
  125.     start = getTime();
  126.     solve_1DKP(&data);
  127.     end = getTime();
  128.     printf("Résultat CPLEX : %.2f\n", data.master.objval);
  129.     printf("Temps CPLEX : %.4f sec\n", end - start);
  130.  
  131.     // Résolution avec la programmation dynamique
  132.     start = getTime();
  133.     int dp_result = dynamicProgramming1DKP(data.b, data.a, data.c, data.n);
  134.     end = getTime();
  135.     printf("Résultat DP : %d\n", dp_result);
  136.     printf("Temps DP : %.4f sec\n", end - start);
  137.  
  138.     // Comparaison des résultats
  139.     if (dp_result == (int)data.master.objval) {
  140.         printf("Les solutions sont identiques.\n");
  141.     } else {
  142.         printf("Les solutions diffèrent.\n");
  143.     }
  144.  
  145.     // Libération de la mémoire
  146.     free(data.c);
  147.     free(data.a);
  148.     free(data.f);
  149.  
  150.     return rval;
  151. }
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Résultat CPLEX : 100.00
Temps CPLEX : 0.0000 sec
Résultat DP : 70
Temps DP : 0.0000 sec
Les solutions diffèrent.
https://ideone.com/89N5Ct
language:
C (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!