Skip to content
Snippets Groups Projects
Select Git revision
  • ed948ae9b79971c1b50acb892bb2dc1afa0f3ff6
  • master default protected
  • release-1.9 protected
  • release-1.10 protected
  • dev protected
  • replication_test
  • 551-init-broker-service-permissions
  • 549-test-oai-pmh
  • 545-saving-multiple-times-breaks-pid-metadata
  • 499-standalone-compute-service-2
  • 539-load-tests
  • hotfix/helm-chart
  • luca_ba_new_interface
  • 534-bug-when-adding-access-to-user-that-is-not-registered-at-dashboard-service
  • release-1.8 protected
  • 533-integrate-semantic-recommendation
  • feature/openshift
  • 518-spark-doesn-t-map-the-headers-correct
  • 485-fixity-checks
  • 530-various-schema-problems-with-subsets
  • release-1.7 protected
  • v1.10.1 protected
  • v1.10.0-rc13 protected
  • v1.10.0-rc12 protected
  • v1.10.0-rc11 protected
  • v1.10.0-rc10 protected
  • v1.10.0-rc9 protected
  • v1.10.0-rc8 protected
  • v1.10.0-rc7 protected
  • v1.10.0-rc6 protected
  • v1.10.0-rc5 protected
  • v1.10.0-rc4 protected
  • v1.10.0-rc3 protected
  • v1.10.0-rc2 protected
  • v1.10.0rc1 protected
  • v1.10.0rc0 protected
  • v1.10.0 protected
  • v1.9.3 protected
  • v1.9.2 protected
  • v1.9.2-rc0 protected
  • v1.9.1 protected
41 results

.env.unix.example

Blame
  • BinPack.cpp 24.74 KiB
    /* (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;
    }