Skip to content
Snippets Groups Projects
Select Git revision
  • 7d3497372c5125fa59720e1479a03e0c129adb34
  • release default protected
  • workshop
3 results

start_config_editor

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;