fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <time.h>
  5.  
  6. typedef struct {
  7.     int n, b, g;
  8.     int *c, *a, *f;
  9. } dataSet;
  10.  
  11. void freeDataset(dataSet* dsptr) {
  12.     free(dsptr->c);
  13.     free(dsptr->a);
  14.     free(dsptr->f);
  15. }
  16.  
  17. int read_TP2_instance_from_string(const char* content, dataSet* dsptr) {
  18.     int n, b, g;
  19.     const char* ptr = content;
  20.  
  21.     if (sscanf(ptr, "%d,%d,%d", &n, &b, &g) != 3) return -1;
  22.  
  23.     dsptr->n = n;
  24.     dsptr->b = b;
  25.     dsptr->g = g;
  26.  
  27.     dsptr->c = malloc(sizeof(int) * n);
  28.     dsptr->a = malloc(sizeof(int) * n);
  29.     dsptr->f = malloc(sizeof(int) * n);
  30.  
  31.     int line = 0;
  32.     while (*ptr && line < n) {
  33.         // Avancer à la ligne suivante
  34.         while (*ptr && *ptr != '\n') ptr++;
  35.         if (*ptr) ptr++;
  36.  
  37.         if (sscanf(ptr, "%d,%d,%d", &dsptr->c[line], &dsptr->a[line], &dsptr->f[line]) != 3)
  38.             break;
  39.         line++;
  40.     }
  41.  
  42.     return (line == n) ? 0 : -1;
  43. }
  44.  
  45. int dynamicProgramming1DKP(int capacity, int* weights, int* values, int n) {
  46.     int* dp = calloc(capacity + 1, sizeof(int));
  47.     for (int i = 0; i < n; i++) {
  48.         for (int w = capacity; w >= weights[i]; w--) {
  49.             if (dp[w - weights[i]] + values[i] > dp[w]) {
  50.                 dp[w] = dp[w - weights[i]] + values[i];
  51.             }
  52.         }
  53.     }
  54.     int result = dp[capacity];
  55.     free(dp);
  56.     return result;
  57. }
  58.  
  59. int main() {
  60.     const char* instance_data =
  61.         "5,15,10\n"
  62.         "10,5,2\n"
  63.         "40,4,1\n"
  64.         "30,6,3\n"
  65.         "50,3,4\n"
  66.         "35,2,2\n";
  67.  
  68.     dataSet data;
  69.     if (read_TP2_instance_from_string(instance_data, &data) != 0) {
  70.         fprintf(stderr, "Failed to read instance data.\n");
  71.         return 1;
  72.     }
  73.  
  74.     printf("Instance loaded: %d items, capacity b = %d\n", data.n, data.b);
  75.     printf("i\tvalue\tweight\n");
  76.     for (int i = 0; i < data.n; i++) {
  77.         printf("%d\t%d\t%d\n", i, data.c[i], data.a[i]);
  78.     }
  79.  
  80.     int result = dynamicProgramming1DKP(data.b, data.a, data.c, data.n);
  81.     printf("Optimal value (1D Knapsack): %d\n", result);
  82.  
  83.     freeDataset(&data);
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Instance loaded: 5 items, capacity b = 15
i	value	weight
0	10	5
1	40	4
2	30	6
3	50	3
4	35	2
Optimal value (1D Knapsack): 155
https://ideone.com/lhaJnC
language:
C (gcc 8.3)
created:
12 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!