A wrapper class for instance data
| 53 | |
| 54 | /// A wrapper class for instance data |
| 55 | class Spec { |
| 56 | protected: |
| 57 | /// Raw instance data |
| 58 | const int* data; |
| 59 | /// Lower and upper bound |
| 60 | int l, u; |
| 61 | public: |
| 62 | /// Whether a valid specification has been found |
| 63 | bool valid(void) const { |
| 64 | return data != nullptr; |
| 65 | } |
| 66 | /// Return maximal capacity of a bin |
| 67 | int capacity(void) const { |
| 68 | return data[0]; |
| 69 | } |
| 70 | /// Return number of items |
| 71 | int items(void) const { |
| 72 | return data[1]; |
| 73 | } |
| 74 | /// Return size of item \a i |
| 75 | int size(int i) const { |
| 76 | return data[i+2]; |
| 77 | } |
| 78 | protected: |
| 79 | /// Find instance by name \a s |
| 80 | static const int* find(const char* s) { |
| 81 | for (int i=0; name[i] != nullptr; i++) |
| 82 | if (!strcmp(s,name[i])) |
| 83 | return bpp[i]; |
| 84 | return nullptr; |
| 85 | } |
| 86 | /// Compute lower bound |
| 87 | int clower(void) const { |
| 88 | /* |
| 89 | * The lower bound is due to: S. Martello, P. Toth. Lower bounds |
| 90 | * and reduction procedures for the bin packing problem. |
| 91 | * Discrete and applied mathematics, 28(1):59-70, 1990. |
| 92 | */ |
| 93 | const int c = capacity(), n = items(); |
| 94 | int l = 0; |
| 95 | |
| 96 | // Items in N1 are from 0 ... n1 - 1 |
| 97 | int n1 = 0; |
| 98 | // Items in N2 are from n1 ... n12 - 1, we count elements in N1 and N2 |
| 99 | int n12 = 0; |
| 100 | // Items in N3 are from n12 ... n3 - 1 |
| 101 | int n3 = 0; |
| 102 | // Free space in N2 |
| 103 | int f2 = 0; |
| 104 | // Total size of items in N3 |
| 105 | int s3 = 0; |
| 106 | |
| 107 | // Initialize n12 and f2 |
| 108 | for (; (n12 < n) && (size(n12) > c/2); n12++) |
| 109 | f2 += c - size(n12); |
| 110 | |
| 111 | // Initialize n3 and s3 |
| 112 | for (n3 = n12; n3 < n; n3++) |