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());
142 for (
int i=n;
i--; ) {
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;
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()],
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());
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;
359 if (bs.
size() == 0) {
361 for (
int i=l.
size();
i--; )
364 }
else if (l.
size() == 0) {
370 for (
int i=bs.
size();
i--; ) {
376 for (
int j=l.
size(); j--; ) {
380 (void)
new (home)
Pack(home,l,bs);