40 namespace Gecode {
namespace Int {
namespace BinPacking {
54 return new (home)
Pack(home,share,*
this);
79 : _nq(region.alloc<int>(m)), _n_nq(0), _eq(-1) {}
96 }
else if (
_eq >= 0) {
121 int* s = region.
alloc<
int>(m);
130 for (
int i=0;
i<
n;
i++)
132 int j =
bs[
i].bin().val();
133 l[j].offset(
l[j].offset() -
bs[
i].
size());
137 s[j.val()] +=
bs[
i].size();
142 for (
int i=n;
i--; ) {
145 s[j.val()] +=
bs[
i].size();
151 for (
int j=m; j--; ) {
154 min -=
l[j].max(); max -=
l[j].min();
158 for (
bool mod =
true;
mod; ) {
160 for (
int j=m; j--; ) {
161 int lj_min =
l[j].min();
162 me =
l[j].gq(home, min +
l[j].
max());
166 max += lj_min -
l[j].min();
mod =
true;
168 int lj_max =
l[j].max();
169 me =
l[j].lq(home, max +
l[j].
min());
173 min += lj_max -
l[j].max();
mod =
true;
179 assert(
l.assigned());
188 for (
int i=0;
i<
n;
i++) {
190 if (
bs[
i].
size() >
l[j.val()].max())
192 if (s[j.val()] -
bs[
i].size() <
l[j.val()].min())
198 int j =
bs[
i].bin().val();
199 l[j].offset(
l[j].offset() -
bs[
i].
size());
226 for (
int i=0;
i<
n;
i++) {
232 for (
int j=m; j--; ) {
234 if (
nosum(static_cast<SizeSet&>(s[j]),
l[j].
min(),
l[j].
max()))
238 if (
nosum(static_cast<SizeSet&>(s[j]),
l[j].
min(),
l[j].
min(),
242 if (
nosum(static_cast<SizeSet&>(s[j]),
l[j].
max(),
l[j].
max(),
250 for (
int i=0;
i<
n;
i++) {
256 if (
nosum(s[j.val()],
257 l[j.val()].min() -
bs[
i].size(),
258 l[j.val()].max() -
bs[
i].size()))
261 if (
nosum(s[j.val()],
l[j.val()].min(),
l[j.val()].max()))
266 int j =
bs[
i].bin().val();
267 l[j].offset(
l[j].offset() -
bs[
i].
size());
282 int c =
bs[0].size();
287 int* n_s = region.
alloc<
int>(c+1);
289 for (
int i=c+1;
i--; )
301 if (
l[j].
max() < 0) {
303 }
else if (c >
l[j].
max()) {
304 n_s[c -
l[j].max()]++; nm++;
308 int* s = region.
alloc<
int>(nm);
313 for (
int i=c+1;
i--; )
314 for (
int n=n_s[
i]; n--; )
331 for (; (n12 < nm) && (s[n12] > c/2); n12++)
335 for (n3 = n12; n3 < nm; n3++)
339 for (
int k=0; k<=c/2; k++) {
341 for (; (n1 < nm) && (s[n1] > c-k); n1++)
345 for (; (s[n3-1] < k) && (n3 > n12); n3--)
348 int o = (s3 > f2) ? ((s3 - f2 + c - 1) /
c) : 0;
362 while (bs[n-1].
size() == 0)
366 if (bs.
size() == 0) {
368 for (
int i=l.
size();
i--; )
371 }
else if (l.
size() == 0) {
377 for (
int i=bs.
size();
i--; ) {
383 for (
int j=l.
size(); j--; ) {
387 (void)
new (home)
Pack(home,l,bs);