fork download
copy 
  1. /*Continuous knapsack Problem
  2. (fractional knapsack problem)
  3. ---------------------------
  4. Given a set of items, each with a weight and a value,
  5. determine a subset of items to include in a collection so that the total weight
  6. is less than or equal to a given limit and the  total value is as large as possible.
  7.  
  8. Se considera un rucsac de capacitate M si N obiecte, ale
  9. caror greutate si valoare sunt date. Sa se gaseasca
  10. o modalitate de a introduce cat mai multe obiecte in rucsac,
  11. astfel incat valoarea globala sa fie maxima. Se considera ca
  12. obiectele poti fi fractionate. Presupunem ca datele de intrare
  13. sunt corecte si valorile obiectelor sunt strict pozitive. Pe prima
  14. linie a fisierului de intrare obiecte.in se gaseste
  15. capacitatea rucsacului. Numarul maxim de obiecte este 50.
  16.  
  17. obiecte.in
  18. 41
  19. 12.34 123.99
  20. 23.45 600.54
  21. 12.78 90.67
  22. 9.34 45.32
  23.  
  24. rucsac.out
  25. In rucsac vor fi introduse obiecte:
  26. Obiectul 2 23.45 600.54 - complet
  27. Obiectul 1 12.34 123.99 - complet
  28. Obiectul 3: 12.34 123.99 - 5.2 kg (fractionar)
  29. */
  30. #include <stdio.h>
  31. #include <malloc.h>
  32. #include <stdbool.h>
  33.  
  34. typedef bool (*comparer)(const void *a, const void *b);
  35.  
  36. typedef struct {
  37.   float weight,
  38.         value;
  39.   int index;
  40. } Object;
  41.  
  42. void read(Object *ob, int *n, float *capacity){
  43.  
  44.      float w,v;
  45.      scanf("%f", capacity);
  46.      while(scanf("%f",&w) == 1) {
  47.          scanf("%f", &v);
  48.          ob[(*n)].weight = w;
  49.          ob[(*n)].value = v;
  50.          ob[(*n)].index = (*n);
  51.          (*n)++;
  52.      }
  53. }
  54.  
  55. void bubblesort(Object *ob, int n, comparer comp) {
  56.  
  57.       bool finished = false;
  58.  
  59.         while(!finished) {
  60.             bool swapped = false;
  61.  
  62.             for(int i = 0; i < n - 1; ++i) {
  63.  
  64.                 if( comp(&ob[i], &ob[i+1])) {
  65.                     Object temp = ob[i];
  66.                            ob[i] = ob[i+1];
  67.                            ob[i+1] = temp;
  68.                            swapped = true;
  69.                 }
  70.             }
  71.             if( swapped ) {
  72.               n--;
  73.             } else {
  74.               finished = true;
  75.             }
  76.         }
  77. }
  78.  
  79. bool descending(const void *a, const void *b) {
  80.  
  81.      Object *o1 = (Object*)a;
  82.      Object *o2 = (Object*)b;
  83.  
  84.      return o2->value/o2->weight - o1->value/o1->weight > 0;
  85. }
  86.  
  87. int main(int argc, char const *argv[]) {
  88.  
  89.   int count = 0;
  90.  
  91.   float capacity;
  92.  
  93.   Object arr[100];
  94.  
  95.   read(arr, &count, &capacity);
  96.  
  97.   printf("%d %f\n", count, capacity);
  98.  
  99.   bubblesort( arr, count, descending );
  100.  
  101.   int i = 0;
  102.  
  103.   while(capacity>0) {
  104.  
  105.     if(arr[i].weight < capacity) {
  106.  
  107.       capacity -= arr[i].weight;
  108.  
  109.       i++;
  110.  
  111.     } else {
  112.  
  113.       capacity = -capacity;
  114.     }
  115.   }
  116.  
  117.   printf("%f\n", capacity);
  118.  
  119.   for(int j = 0; j < i; j++) {
  120.  
  121.       printf("%d: %.4f %.4f completed object\n", arr[j].index,arr[j].weight, arr[j].value);
  122.   }
  123.  
  124.   if(capacity<0) {
  125.  
  126.      printf("%d: %.4f %.4f fractional object %f\n", arr[i].index,arr[i].weight, arr[i].value, capacity);
  127.   }
  128.  
  129.   return 0;
  130. }
  131.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
41
12.34 123.99
23.45 600.54
12.78 90.67
9.34 45.32
stdout
copy 
4 41.000000
-5.209999
1: 23.4500 600.5400 completed object
0: 12.3400 123.9900 completed object
2: 12.7800 90.6700 fractional object -5.209999
https://ideone.com/oaoo2H
Knapsack Continous Problem
language:
C (gcc 8.3)
created:
1 year ago
visibility:
secret

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!