/* (C) Copyright 2003 Jens Lysgaard. All rights reserved. */
/* OSI Certified Open Source Software */
/* This software is licensed under the Common Public License Version 1.0 */

#include <stdlib.h>
#include <stdio.h>
#include "memmod.h"
#include "basegrph.h"
#include "sort.h"

void BP_FirstFit(int CAP,
                 int *ItemSize,
                 int n,
                 int *Bin,
                 int *NoOfBins)
{
  /* This is the First-Fit heuristic algorithm for the
     Bin Packing Problem. If the items are ordered in nonincreasing order,
     the algorithm is the First-Fit Decreasing algorithm.
     Return values: Bin[i] is the number of the bin into which
     item i is packed. */

  int i,Item,BinNr,UsedBins;
  int *Slack;

  /* printf("BEGIN BP_FirstFit\n"); */

  Slack = MemGetIV(n+1);

  UsedBins = 0;

  for (Item=1; Item<=n; Item++)
  {
    BinNr = 0;
    for (i=1; i<=UsedBins; i++)
    {
      if (Slack[i] >= ItemSize[Item])
      {
        BinNr = i;
        break;
      }
    }

    /* printf("Item %d: BinNr = %d\n",Item,BinNr); */

    if (BinNr == 0)
    {
      UsedBins++;
      Slack[UsedBins] = CAP;
      BinNr = UsedBins;
      /* printf("New bin %d\n",BinNr); */
    }

    Bin[Item] = BinNr;
    Slack[BinNr] -= ItemSize[Item];

    /* printf("Slack(%d) = %d\n",BinNr,Slack[BinNr]); */
  }

  /*
  printf("UsedBins = %d\n",UsedBins);
  printf("Bin =");
  for (i=1; i<=n; i++) printf(" %d",Bin[i]);
  printf("\n");
  printf("Slack =");
  for (i=1; i<=UsedBins; i++) printf(" %d",Slack[i]);
  printf("\n");
  */

  *NoOfBins = UsedBins;

  MemFree(Slack);

  /* printf("END BP_FirstFit(Bins=%d)\n",*NoOfBins); */
}

void BP_ModifiedFirstFit(int CAP,
                         int *ItemSize,
                         int n,
                         int *Bin,
                         int *NoOfBins)
{
  /* This is the First-Fit heuristic algorithm for the
     Bin Packing Problem. If the items are ordered in nonincreasing order,
     the algorithm is the First-Fit Decreasing algorithm.
     Return values: Bin[i] is the number of the bin into which
     item i is packed. If Bin[i] > 0 on input, then that allocation is
     fixed. */

  int i,Item,BinNr,UsedBins;
  int *Slack;

  /*
  printf("BEGIN BP_ModifiedFirstFit: CAP=%d, n=%d\n",CAP,n);
  printf("ItemSize =");
  for (i=1; i<=n; i++) printf(" %d",ItemSize[i]);
  printf("\n");
  */

  Slack = MemGetIV(n+1);

  UsedBins = 0;

  for (Item=1; Item<=n; Item++)
  if (Bin[Item] > 0)
  {
    if (Bin[Item] > UsedBins)
    {
      for (i=UsedBins+1; i<=Bin[Item]; i++) Slack[i] = CAP;
      UsedBins = Bin[Item];
    }

    Slack[Bin[Item]] -= ItemSize[Item];
  }

  for (Item=1; Item<=n; Item++)
  {
    if (Bin[Item] > 0) continue;

    BinNr = 0;
    for (i=1; i<=UsedBins; i++)
    {
      if (Slack[i] >= ItemSize[Item])
      {
        BinNr = i;
        break;
      }
    }

    /* printf("Item %d: BinNr = %d\n",Item,BinNr); */

    if (BinNr == 0)
    {
      UsedBins++;
      Slack[UsedBins] = CAP;
      BinNr = UsedBins;
      /* printf("New bin %d\n",BinNr); */
    }

    Bin[Item] = BinNr;
    Slack[BinNr] -= ItemSize[Item];

    /* printf("Slack(%d) = %d\n",BinNr,Slack[BinNr]); */
  }

  /*
  printf("UsedBins = %d\n",UsedBins);
  printf("Bin =");
  for (i=1; i<=n; i++) printf(" %d",Bin[i]);
  printf("\n");
  printf("Slack =");
  for (i=1; i<=UsedBins; i++) printf(" %d",Slack[i]);
  printf("\n");
  */

  *NoOfBins = UsedBins;

  MemFree(Slack);

  /*
  printf("FFD: Bin =");
  for (i=1; i<=n; i++) printf(" %d",Bin[i]);
  printf("\n");
  */

  /* printf("END BP_ModifiedFirstFit(Bins=%d)\n",*NoOfBins); */
}



void BP_DominancePacking(int CAP,
                         int *ItemSize,
                         int n,
                         int *Bin,
                         int *NoOfBins)
{
  /* This is the reduction algorithm in Martello & Toth
     ("Knapsack Problems", 1990, pp. 233-234), based on dominance
     between different packings.
       On return, Bin[i] is the bin number in which item i has been packed.
     If Bin[i] = 0, then item i has not been packed into a bin. The
     remaining items are therefore those with Bin[i] = 0.
       NoOfBins is the number of bins that have been optimally packed.

     It is assumed that on input the items are sorted in nonincreasing
     order of size, i.e., ItemSize[i] >= ItemSize[i+1], and that
     all items are <= the capacity CAP.
  */

  int i,j,k,r,s,PrevJ,JStar;
  int UsedBins,RemainingWeight,LimitSize,SumSize,CapForS;
  int BestR,BestS,PrevR,PrevS,BestSum;
  int ItemsBetweenRS,SumPairBetweenRS;

  /*
  printf("BP_DominancePacking: Input:\n");
  printf("CAP=%d, n=%d\n",CAP,n);
  printf("ItemSize =");
  for (i=1; i<=n; i++) printf(" %d",ItemSize[i]);
  printf("\n");
  */

  RemainingWeight = 0;
  UsedBins = 0;
  PrevJ = 0;

  for (i=1; i<=n; i++)
  {
    Bin[i] = 0;
    RemainingWeight += ItemSize[i];
  }

  while ((PrevJ < n) && (RemainingWeight > CAP))
  {
    j = 0;
    for (i=PrevJ+1; i<=n; i++)
    {
      if (Bin[i]==0)
      {
        j = i;
        break;
      }
    }

    if (j == 0) break;
    PrevJ = j;

    LimitSize = CAP - ItemSize[j];

    JStar = 0;
    for (i=1; i<=n; i++)
    if ((i!=j) && (Bin[i]==0))
    {
      if (ItemSize[i] <= LimitSize)
      {
        JStar = i;
        break;
      }
    }

    if (JStar == 0)
    { /* Packing of item j as the only item into a bin */
      UsedBins++;
      Bin[j] = UsedBins;
      RemainingWeight -= ItemSize[j];
    }
    else
    {
      /* Find the maximum number of items (k) that can be packed together
         with item j. */

      k=0;
      SumSize=0;

      if (ItemSize[JStar] != LimitSize)
      {
        for (i=n; i>=JStar; i--)
        if (i!=j)
        {
          if (Bin[i]==0)
          {
            SumSize += ItemSize[i];
            k++;
            if (SumSize > LimitSize)
            {
              k--;
              break;
            }
            if (k == 3) break;
          }
        }
      }

      if ((k==1) || (ItemSize[JStar] == LimitSize))
      {
        /* Packing of items j and JStar as the only two items into a bin */
        UsedBins++;
        Bin[j] = UsedBins;
        RemainingWeight -= ItemSize[j];
        Bin[JStar] = UsedBins;
        RemainingWeight -= ItemSize[JStar];
      }
      else
      if (k==2)
      {
        /* Left pointer is r, right pointer is s. */

        for (s=n; s>=JStar; s--)
        {
          if ((s!=j) && (Bin[s]==0))
          break;
        }

        /* s is the index of the smallest item */

        for (r=JStar; r<s; r++)
        {
          if ((r!=j) &&
              (Bin[r]==0) && ((ItemSize[r] + ItemSize[s]) <= LimitSize))
          break;
        }

        /* r is the index of the biggest item that can be packed
           together with items j and s */

        BestSum = ItemSize[r] + ItemSize[s];
        BestR = r;
        BestS = s;

        PrevR = r;
        PrevS = s;

        /* The previous r-value is included in the interval for r in
           the following loop, as the biggest item s that can be packed
           together with j and r has not (necessarily) been found yet */

        for (r=PrevR; r<PrevS; r++)
        {
          if ((r!=j) && (Bin[r]==0))
          {
            /* Find the biggest item s that can be packed together with
               j and r */

            CapForS = LimitSize - ItemSize[r];

            for (s=PrevS-1; s>r; s--)
            {
              if ((s!=j) && (Bin[s]==0))
              {
                if (ItemSize[s] > CapForS) break;

                if (ItemSize[s] + ItemSize[r] > BestSum)
                {
                  BestSum = ItemSize[s] + ItemSize[r];
                  BestR   = r;
                  BestS   = s;
                }
              }
            }

            PrevS = BestS;
          }
        }

        /* End of search for k=2 */

        if (ItemSize[JStar] >= BestSum)
        {
          /* JStar is better than r+s */
          /* Packing of items j and JStar as the only two items into a bin */

          UsedBins++;
          Bin[j] = UsedBins;
          RemainingWeight -= ItemSize[j];
          Bin[JStar] = UsedBins;
          RemainingWeight -= ItemSize[JStar];
        }
        else
        if (BestR == JStar)
        {
          ItemsBetweenRS = 0;
          SumPairBetweenRS = 0;

          for (i=BestS-1; i>BestR; i--)
          {
            if ((i!=j) && (Bin[i]==0))
            {
              if ((ItemSize[i] != ItemSize[BestR]) &&
                  (ItemSize[i] != ItemSize[BestS]))
              {
                ItemsBetweenRS++;
                SumPairBetweenRS += ItemSize[i];

                if (ItemsBetweenRS == 2) break;
              }
            }
          }

          if ((ItemsBetweenRS <= 1) || (SumPairBetweenRS > LimitSize))
          {
            /* Packing of items j, BestR and BestS as the
               only three items into a bin */

            UsedBins++;
            Bin[j] = UsedBins;
            RemainingWeight -= ItemSize[j];
            Bin[BestR] = UsedBins;
            RemainingWeight -= ItemSize[BestR];
            Bin[BestS] = UsedBins;
            RemainingWeight -= ItemSize[BestS];
          }
        }
      } /* k = 2 */
    }
  }

  if (RemainingWeight <= CAP)
  {
    /* Pack the remaining items into one bin */
    UsedBins++;
    for (i=1; i<=n; i++)
    {
      if (Bin[i] == 0)
      Bin[i] = UsedBins;
    }
  }

  *NoOfBins = UsedBins;

  /*
  printf("NoOfBins = %d\n",*NoOfBins);
  if ((*NoOfBins) > 0)
  {
    printf("Bin =");
    for (i=1; i<=n; i++) printf(" %d",Bin[i]);
    printf("\n");
  }
  */

  /* printf("END BP_DominancePacking: NoOfBins = %d\n",*NoOfBins); */
}


void BP_MTL2(int CAP,
             int *ItemSize,
             int n,
             int *LB)
{
  /* This is the bounding procedure L2 in Martello & Toth
     ("Knapsack Problems", 1990, pp. 231-232).
       It is assumed that on input the items are sorted in nonincreasing
     order of size, i.e., ItemSize[i] >= ItemSize[i+1], and that
     all items are <= the capacity CAP.
  */

  int i,JStar,CJ12,SJStar,CJ2,SJ2,SJ3,JPrime,JDPrime;
  int /*CAPHalf,*/ SumAllItems,CAPSum,Limit,AddBins,AddCAP,AddSizeSum;
  int L2;


  /*
  printf("BP_MTL2: Input:\n");
  printf("CAP=%d, n=%d\n",CAP,n);
  printf("ItemSize =");
  for (i=1; i<=n; i++) printf(" %d",ItemSize[i]);
  printf("\n");
  */

  /*
  CAPHalf = CAP / 2;
  if (ItemSize[n] > CAPHalf)
  {
    *LB = n;
    return;
  }
  */

  if ((ItemSize[n-1] + ItemSize[n]) > CAP)
  {
    *LB = n;
    return;
  }


  for (i=1; i<=n; i++)
  {
    /*
    if (ItemSize[i] < CAPHalf)
    {
      JStar = i;
      break;
    }
    */

    if ((ItemSize[i] * 2) <= CAP)
    {
      JStar = i;
      break;
    }

  }

  /* printf("JStar = %d\n",JStar); */

  if (JStar == 1)
  {
    /* The bound reduces to the trivial lower bound L1 */
    SumAllItems = 0;
    for (i=1; i<=n; i++) SumAllItems += ItemSize[i];

    (*LB) = 1;
    CAPSum = CAP;
    while (CAPSum < SumAllItems)
    {
      (*LB)++;
      CAPSum += CAP;
    }

    /* printf("Trivial bound L2:= %d\n",*LB); */
    return;
  }

  CJ12 = JStar - 1;

  SJStar = 0;
  for (i=JStar; i<=n; i++) SJStar += ItemSize[i];

  JPrime = 0;
  Limit = CAP - ItemSize[JStar];
  for (i=1; i<JStar; i++)
  {
    if (ItemSize[i] <= Limit)
    {
      JPrime = i;
      break;
    }
  }

  if (JPrime == 0) JPrime = JStar;

  CJ2 = JStar - JPrime;

  SJ2 = 0;
  for (i=JPrime; i<JStar; i++) SJ2 += ItemSize[i];

  JDPrime = JStar;
  SJ3 = ItemSize[JDPrime];

  if (JDPrime < n)
  {
    while (ItemSize[JDPrime+1] == ItemSize[JDPrime])
    {
      JDPrime++;
      SJ3 += ItemSize[JDPrime];
      if (JDPrime == n) break;
    }
  }

  L2 = CJ12;

  do
  {
    AddSizeSum = SJ3 + SJ2 - (CJ2 * CAP);
    AddBins = 0;
    AddCAP = 0;

    while (AddCAP < AddSizeSum)
    {
      AddBins++;
      AddCAP += CAP;
    }

    if ((CJ12 + AddBins) > L2)
    L2 = (CJ12 + AddBins);

    JDPrime++;
    if (JDPrime > n) break;

    SJ3 += ItemSize[JDPrime];

    if (JDPrime < n)
    {
      while (ItemSize[JDPrime+1] == ItemSize[JDPrime])
      {
        JDPrime++;
        SJ3 += ItemSize[JDPrime];
        if (JDPrime == n) break;
      }
    }

    if (JPrime > 1)
    {
      Limit = CAP - ItemSize[JDPrime];
      while (ItemSize[JPrime-1] <= Limit)
      {
        JPrime--;
        CJ2++;
        SJ2 += ItemSize[JPrime];
        if (JPrime == 1) break;
      }
    }
  } while (JDPrime <= n);

  *LB = L2;

  /* printf("BP_MTL2: L2 = %d\n",L2); */
  /* printf("BP_MTL2: END\n"); */
}

void BP_ModifiedMTL3(int CAP,
                     int *ItemSize,
                     int n,
                     int UB,
                     int *LB)
{
  int i,j,k,nBar;
  int L3,Z,Zr,L2;
  int *W, *Bin;

  /*
  printf("BP_ModifiedMTL3: Input:\n");
  printf("UB=%d, CAP=%d, n=%d\n",UB,CAP,n);
  printf("ItemSize =");
  for (i=1; i<=n; i++) printf(" %d",ItemSize[i]);
  printf("\n");
  */

  W = MemGetIV(n+1);
  Bin = MemGetIV(n+1);

  for (i=1; i<=n; i++) W[i] = ItemSize[i];

  L3 = 0;
  Z = 0;
  nBar = n;

  while (nBar >= 1)
  {
    BP_DominancePacking(CAP,W,nBar,Bin,&Zr);

    if (Zr > 0)
    {
      Z += Zr;

      k = 0;
      for (j=1; j<=nBar; j++)
      {
        if (Bin[j] == 0)
        {
          k++;
          W[k] = W[j];
        }
      }

      nBar = k;
    }

    if (nBar == 0)
    L2 = 0;
    else
    BP_MTL2(CAP,W,nBar,&L2);

    if (L3 < (Z + L2))
    L3 = (Z + L2);

    if (L3 >= UB) break;

    /* nBar--; */
    nBar = 0; /* Skip the relaxations */
  }

  *LB = L3;

  MemFree(W);
  MemFree(Bin);

  /* printf("END BP_ModifiedMTL3 = %d\n",L3); */
}

void BP_ExactBinPacking(int CAP,
                        int *ItemSize,
                        int n,
                        int *LB,
                        int *UB,
                        int *Bin)
{
  char ComputeBound;
  int i,j,Item,ThisBin,NewBin,LoopNr;
  int MinItemSize,MaxTotalSlack,TotalItemSizeSum,AccSlack;
  int FirstCandidateBin;
  int TmpMaxSize,TmpIndex;
  int LowerBoundBins,UpperBoundBins,TmpLowerBound,TmpUpperBound;
  int CompressedItems,CompressedBins;
  int *BestBin, *B, *BinSlack, *W, *TmpBin;
  int **MinItem;


  /*
  printf("BEGIN BP_ExactBinPacking(NoOfItems=%d, CAP=%d)\n",n,CAP);
  printf("ItemSize =");
  for (i=1; i<=n; i++) printf(" %d",ItemSize[i]);
  printf("\n");
  */

  BestBin = MemGetIV(n+1);
  B = MemGetIV(n+1);
  BinSlack = MemGetIV(n+1);
  W = MemGetIV(n+1);
  TmpBin = MemGetIV(n+1);

  BP_FirstFit(CAP,ItemSize,n,BestBin,&UpperBoundBins);
  for (i=1; i<=n; i++) Bin[i] = BestBin[i];

  /* printf("UpperBoundBins = %d\n",UpperBoundBins); */

  MinItem = MemGetIM(n+1,UpperBoundBins+1);

  /* printf("Calling MTL2\n"); */
  BP_MTL2(CAP,ItemSize,n,&LowerBoundBins);

  /* printf("MTL2 = %d\n",LowerBoundBins); */

  /*
  if (LowerBoundBins < UpperBoundBins)
  BP_ModifiedMTL3(CAP,ItemSize,n,UpperBoundBins,&LowerBoundBins);
  */

  LoopNr = 0;

  if (LowerBoundBins == UpperBoundBins)
  {
    goto EndOfExactBinPacking;
  }

  /* If we get to here, UpperBoundBins is at least 3. */

  MinItemSize = ItemSize[n];
  /* printf("MinItemSize = %d\n",MinItemSize); */
  if (MinItemSize <= 0) exit(0);

  TotalItemSizeSum = 0;
  for (i=1; i<=n; i++) TotalItemSizeSum += ItemSize[i];

  /* printf("TotalItemSizeSum = %d\n",TotalItemSizeSum); */

  MaxTotalSlack = ((UpperBoundBins-1) * CAP) - TotalItemSizeSum;
  /* Max. slack, if a better solution than the currently best solution
     is to be found. */

  /* printf("MaxTotalSlack = %d\n",MaxTotalSlack); */

  /* Find the minimum level at which a different allocation must be
     made if a better solution than the currently best exists. */

  for (i=1; i<=n; i++) BinSlack[i] = CAP;

  AccSlack = 0;
  Item = 0;

  for (i=1; i<=n-1; i++)
  {
    ThisBin = BestBin[i];
    B[i] = ThisBin;
    BinSlack[ThisBin] -= ItemSize[i];

    if (BinSlack[ThisBin] < MinItemSize)
    {
      AccSlack += BinSlack[ThisBin];
      if (AccSlack > MaxTotalSlack)
      {
        Item = i;
        break;
      }
    }

    if (ThisBin <= UpperBoundBins-2)
    {
      Item = i;
    }
  }

  /* printf("Initial Item = %d, AccSlack=%d\n",Item,AccSlack); */

  /* Redo the stuff until this Item */
  for (i=1; i<=n; i++) BinSlack[i] = CAP;
  for (i=1; i<=n; i++) B[i] = 0;

  AccSlack = 0;

  for (i=1; i<=Item; i++)
  {
    ThisBin = BestBin[i];
    B[i] = ThisBin;
    /* printf("B(%d):= %d\n",i,B[i]); */
    BinSlack[ThisBin] -= ItemSize[i];
    /* printf("BinSlack(%d):= %d\n",ThisBin,BinSlack[ThisBin]); */
    if (BinSlack[ThisBin] < MinItemSize)
    AccSlack += BinSlack[ThisBin];
  }

  /* printf("Item = %d, AccSlack=%d\n",Item,AccSlack); */

  for (i=0; i<=n; i++)
  for (j=1; j<=UpperBoundBins; j++)
  MinItem[i][j] = i+1;

  BinSlack[0] = -1; /* => Different from CAP */

  LoopNr = 0;

  do
  {
    LoopNr++;
    /* Reallocate item */
    /* printf("Top of do loop...: LoopNr=%d\n",LoopNr); */
    /* Remove the item from its current bin */
    ThisBin = B[Item];

    /* printf("Item=%d, ThisBin=%d\n",Item,ThisBin); */

    if (ThisBin > 0)
    if (BinSlack[ThisBin] < MinItemSize)
    {
      /*
      printf("Item closed bin: BinSlack(%d)=%d, MinItemSize=%d\n",
              ThisBin,BinSlack[ThisBin],MinItemSize);
      */

      /* This item closed ThisBin when it was allocated to this bin */
      /* Some dominated allocations may be derived */

      AccSlack -= BinSlack[ThisBin];

      /* printf("AccSlack:= %d\n",AccSlack); */

      /* Find the first item j for which w(j)+w(n) fits into the bin
         instead of the current item. Item j is the first nondominated
         item that can be filled into this bin, given the allocation
         of items 1,...,Item-1. */

      TmpMaxSize = BinSlack[ThisBin] + ItemSize[Item] - ItemSize[n];
      TmpIndex = n+1;

      /* printf("TmpMaxSize=%d\n",TmpMaxSize); */

      for (j=Item+1; j<=n; j++)
      if (ItemSize[j] <= TmpMaxSize)
      {
        TmpIndex = j;
        break;
      }

      MinItem[Item-1][ThisBin] = TmpIndex;
      /* printf("MinItem(%d,%d):= %d\n",Item-1,ThisBin,MinItem[Item-1][ThisBin]); */
    }

    if (ThisBin > 0)
    BinSlack[ThisBin] += ItemSize[Item];

    /* printf("BinSlack(%d):= %d\n",ThisBin,BinSlack[ThisBin]); */

    /* Find the next bin > B[Item] for this item */
    if (BinSlack[ThisBin] == CAP)
    {
      /* The item initialized a bin, so it should not be tried in
         any other bin: move up the tree to the previous item */

      /* printf("Item initialized new bin => NewBin:= 0\n"); */
      NewBin = 0;
      /* Backtrack */
    }
    else
    {
      /* Find the first bin > B[Item] for which the slack before
         allocation of this item into the bin differs from *all*
         smaller-indexed bins. This is also a dominance criterion.
         It may be a new criterion (!).
           The criterion follows from the observation that there is
         no point in assigning this item into a bin which effectively
         is a copy of a smaller-indexed bin.

         The new bin for this item must also satisfy the dominance
         criterion wrt. the MinItem.

         In addition, if w(j) = w(j+1), then item j+1 is required to
         satisfy B(j+1) >= B(j). This is also a new criterion.
       */

      FirstCandidateBin = ThisBin+1;

      /* printf("FirstCandidateBin:= %d\n",FirstCandidateBin); */

      if ((ItemSize[Item] == ItemSize[Item-1]) &&
          (FirstCandidateBin < B[Item-1]))
      {
        FirstCandidateBin = B[Item-1];
        /*
        printf("Identical items %d and %d: Adj. FirstCandidateBin:= %d\n",
                Item,Item-1,FirstCandidateBin);
        */
      }

      NewBin = 0;

      for (j=FirstCandidateBin; j<=UpperBoundBins-1; j++)
      {
        NewBin = j;
        /* printf("Possible bin %d:\n",j); */

        /* printf("MinItem(%d,%d) = %d\n",Item-1,j,MinItem[Item-1][j]); */

        if (BinSlack[j] < ItemSize[Item])
        {
          /*
          printf("ItemSize=%d > BinSlack(%d)=%d\n",
                  ItemSize[Item],j,BinSlack[j]);
          */
          NewBin = 0;
          continue;
        }

        if (Item < MinItem[Item-1][j])
        {
          /* Try next bin */
          /*
          printf("Item < MinItem(%d,%d) = %d\n",Item-1,j,MinItem[Item-1][j]);
          */
          NewBin = 0;
          continue;
        }

        if (NewBin > 0)
        {
          /* printf("Check acc. slack:\n"); */
          /* Check the accumulated BinSlack */
          if ((BinSlack[NewBin] - ItemSize[Item]) < MinItemSize)
          {
            /*
            printf("Item generates slack of %d in bin %d\n",
                    BinSlack[NewBin] - ItemSize[Item],NewBin);
            */
            /* The Item will close the NewBin */
            if ((AccSlack +
                (BinSlack[NewBin] - ItemSize[Item])) > MaxTotalSlack)
            {
              /* printf(" + AccSlack = %d > %d\n",AccSlack,MaxTotalSlack); */
              NewBin = 0;
            }
          }
        }

        if (NewBin > 0)
        {
          for (i=1; i<j; i++)
          {
            if (BinSlack[i] == BinSlack[j])
            {
              /* Try next bin */

              /*
              printf("Equal bin slacks (tried bin %d):\n",j);
              printf("BinSlack(%d) = BinSlack(%d) = %d\n",
                      i,j,BinSlack[i]);
              */

              NewBin = 0;
              break;
            }
          }
        }

        if (NewBin > 0) break;
      }
    }

    /* printf("Item=%d, NewBin:= %d\n",Item,NewBin); */

    if (NewBin > 0)
    {
      /* Assign Item to NewBin */

      B[Item] = NewBin;
      BinSlack[NewBin] -= ItemSize[Item];

      /*
      printf("B(%d):= %d, BinSlack(%d):=%d\n",
              Item,B[Item],NewBin,BinSlack[NewBin]);
      */

      if (BinSlack[NewBin] < MinItemSize)
      {
        AccSlack += BinSlack[NewBin];
        /* printf("AccSlack:= %d\n",AccSlack); */
      }

      /* Compute new lower bound given this allocation */
      ComputeBound = 0;

      CompressedItems = 0;
      for (i=1; i<=UpperBoundBins; i++)
      {
        if (BinSlack[i] < CAP)
        {
          W[++CompressedItems] = (CAP - BinSlack[i]);
          /*
          printf("From Bins: W(%d):= %d\n",
                  CompressedItems,W[CompressedItems]);
          */
          if (W[CompressedItems] != ItemSize[CompressedItems])
          ComputeBound = 1;
        }
      }

      CompressedBins = CompressedItems;

      for (i=Item+1; i<=n; i++)
      {
        W[++CompressedItems] = ItemSize[i];
        /*
        printf("From Item %d: W(%d):= %d\n",
                i,CompressedItems,W[CompressedItems]);
        */
        /* TmpBin[CompressedItems] = 0; */
      }

      /* Compute new feasible solution given this allocation */
      for (i=1; i<=CompressedBins; i++) TmpBin[i] = i;
      for (i=CompressedBins+1; i<=CompressedItems; i++) TmpBin[i] = 0;

      BP_ModifiedFirstFit(CAP,W,CompressedItems,TmpBin,&TmpUpperBound);
      /* printf("FFD => %d bins\n",TmpUpperBound); */

      if (TmpUpperBound < UpperBoundBins)
      {
        UpperBoundBins = TmpUpperBound;
        /* printf("UpperBoundBins:= %d\n",UpperBoundBins); */

        /* for (i=1; i<=Item; i++) printf("B(%d) = %d\n",i,B[i]); */

        /* for (i=1; i<=n; i++) Bin[i] = TmpBin[i]; */
        for (i=Item+1; i<=n; i++) Bin[i] = TmpBin[i-Item+CompressedBins];
        for (i=1; i<=Item; i++) Bin[i] = B[i];

        if (LowerBoundBins == UpperBoundBins)
        goto EndOfExactBinPacking;
      }

      ComputeBound = 1;

      /* Sort items from bins */
      /* SortIVDec(W,CompressedItems); */
      if (CompressedBins > 1)
      SortIVDec(W,CompressedBins);
      /* Sufficient to sort the compressed bins */

      if (ComputeBound == 0)
      {
        /* printf("ComputeBound = 0\n"); */
        TmpLowerBound = LowerBoundBins;
        /* printf("TmpLowerBound = %d\n",TmpLowerBound); */
      }
      else
      {
        BP_MTL2(CAP,W,CompressedItems,&TmpLowerBound);

        if (TmpLowerBound < UpperBoundBins)
        BP_ModifiedMTL3(CAP,W,CompressedItems,UpperBoundBins,&TmpLowerBound);

        /* printf("TmpLowerBound = %d\n",TmpLowerBound); */
      }


      if (TmpLowerBound >= UpperBoundBins)
      {
        /* Try next bin for this item in the next loop */
        /* No action is OK: keep the current item for reallocation to the
           next bin */
      }
      else
      {
        /* Forward step = branch */

        for (i=1; i<=UpperBoundBins; i++)
        MinItem[Item][i] = MinItem[Item-1][i];

        B[Item+1] = 0;
        Item++;
      }
    }
    else
    {
      /* NewBin = 0 */
      /* No more bins need to be tried for this item */
      /* Backtrack */

      B[Item] = 0;
      Item--;
    }

    /* if ((LoopNr % 10) == 0) printf("LoopNr = %d\n",LoopNr); */

  } while ((LoopNr < 1000) && (Item > 1));

  if (Item == 1)
  LowerBoundBins = UpperBoundBins;

  EndOfExactBinPacking:

  *LB = LowerBoundBins;
  *UB = UpperBoundBins;

  /*
  printf("LoopNr=%d, LowerBoundBins=%d, UpperBoundBins=%d\n",
          LoopNr,LowerBoundBins,UpperBoundBins);
  */

  MemFree(BestBin);
  MemFree(B);
  MemFree(BinSlack);
  MemFree(W);
  MemFree(TmpBin);

  MemFreeIM(MinItem,n+1);

  return;
}

