Advertisement
iocoder

Buying books

Aug 25th, 2012
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.43 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <math.h>
  3.  
  4. #define N 7
  5.  
  6. float x[] = {
  7.     11.5,
  8.     12,
  9.     12,
  10.     12.5,
  11.     13,
  12.     13,
  13.     14.5
  14. };
  15.  
  16. char vis[N] = {0};
  17. float temp[N];
  18. int steps[N];
  19. float sol[N];
  20. int solsteps[N];
  21.  
  22. float sum = 0;
  23. float min = 0;
  24. int f = 0;
  25. int mal = 0;
  26.  
  27. float roundar(float param) {
  28.     float fractpart;
  29.     double intpart;
  30.     fractpart = modf (param , &intpart);
  31.     if      (fractpart >= 0.75) fractpart = 0.75;
  32.     else if (fractpart >= 0.5 ) fractpart = 0.5 ;
  33.     else if (fractpart >= 0.25) fractpart = 0.25;
  34.     else    fractpart = 0;
  35.     return param; // optionality...
  36. }
  37.  
  38. void rec(int level, float cobon, float stack) {
  39.     int i;
  40.    
  41.     if (level == N) {
  42.  
  43.         if ((!f) || (sum < min)) {
  44.             f = 1;
  45.             min = sum;
  46.             for (i = 0; i < N; i++) sol[i] = temp[i], solsteps[i] = steps[i];
  47.         }
  48.         return;
  49.     }
  50.  
  51.     for (i = 0; i < N; i++) {
  52.         if (!vis[i]) {
  53.             vis[i] = 1;
  54.             float cost ;
  55.             temp[level] = x[i];
  56.             // there are two possiblities...
  57.             // 1- terminate the stack:
  58.             cost = roundar((1-cobon) * (stack + x[i]));
  59.             sum += cost;
  60.             steps[level] = mal++;
  61.             rec(level+1, (roundar(0.5*cost))/100, 0);
  62.             mal--;
  63.             sum -= cost;
  64.  
  65.             // 2- don't terminate it:
  66.             if (level != N - 1) {
  67.                 rec(level+1, cobon, stack + x[i]);
  68.             }
  69.  
  70.             vis[i] = 0;
  71.         }
  72.     }
  73. }
  74.  
  75.  
  76. int main() {
  77.     int i = 0;
  78.     rec(0, 0, 0);
  79.     printf("min=%f\n", min);
  80.     for (i = 0; i < N; i++)
  81.         printf("%.2f (%d)%s", sol[i], solsteps[i], i==N-1 ? "\n":" => ");  
  82.     return 0;
  83. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement