Return choice
| 279 | } |
| 280 | /// Return choice |
| 281 | virtual Gecode::Choice* choice(Space&) { |
| 282 | assert(!bin[item].assigned()); |
| 283 | |
| 284 | int n = bin.size(), m = load.size(); |
| 285 | |
| 286 | Region region; |
| 287 | |
| 288 | // Free space in bins |
| 289 | int* free = region.alloc<int>(m); |
| 290 | |
| 291 | for (int j=m; j--; ) |
| 292 | free[j] = load[j].max(); |
| 293 | for (int i=n; i--; ) |
| 294 | if (bin[i].assigned()) |
| 295 | free[bin[i].val()] -= size[i]; |
| 296 | |
| 297 | // Equivalent bins with same free space |
| 298 | int* same = region.alloc<int>(m+1); |
| 299 | unsigned int n_same = 0; |
| 300 | unsigned int n_possible = 0; |
| 301 | |
| 302 | // Initialize such that failure is guaranteed (pack into bin -1) |
| 303 | same[n_same++] = -1; |
| 304 | |
| 305 | // Find a best-fit bin for item |
| 306 | int slack = INT_MAX; |
| 307 | for (Int::ViewValues<Int::IntView> j(bin[item]); j(); ++j) |
| 308 | if (size[item] <= free[j.val()]) { |
| 309 | // Item still can fit into the bin |
| 310 | n_possible++; |
| 311 | if (free[j.val()] - size[item] < slack) { |
| 312 | // A new, better fit |
| 313 | slack = free[j.val()] - size[item]; |
| 314 | same[0] = j.val(); n_same = 1; |
| 315 | } else if (free[j.val()] - size[item] == slack) { |
| 316 | // An equivalent bin, remember it |
| 317 | same[n_same++] = j.val(); |
| 318 | } |
| 319 | } |
| 320 | /* |
| 321 | * Domination rules: |
| 322 | * - if the item fits the bin exactly, just assign |
| 323 | * - if all possible bins are equivalent, just assign |
| 324 | * |
| 325 | * Also catches failure: if no possible bin was found, commit |
| 326 | * the item into bin -1. |
| 327 | */ |
| 328 | if ((slack == 0) || (n_same == n_possible) || (slack == INT_MAX)) |
| 329 | return new Choice(*this, 1, item, same, 1); |
| 330 | else |
| 331 | return new Choice(*this, 2, item, same, n_same); |
| 332 | } |
| 333 | /// Return choice |
| 334 | virtual const Gecode::Choice* choice(const Space&, Archive& e) { |
| 335 | int alt, item, n_same; |