Skip to content
Snippets Groups Projects
Select Git revision
  • master
  • laudantium-unde-et-iste-et
  • ea-dolor-quia-et-sint
  • ipsum-consequatur-et-in-et
  • sapiente-et-possimus-neque-est
  • qui-in-quod-nam-voluptatem
  • aut-deleniti-est-voluptatum-repellat
  • modi-et-quam-sunt-consequatur
  • et-laudantium-voluptas-quos-pariatur
  • voluptatem-quia-fugit-ut-perferendis
  • at-adipisci-ducimus-qui-nihil
  • dolorem-ratione-sed-illum-minima
  • inventore-temporibus-ipsum-neque-rerum
  • autem-at-dolore-molestiae-et
  • doloribus-dolorem-quos-adipisci-et
  • sed-sit-tempore-expedita-possimus
  • et-recusandae-deleniti-voluptas-consectetur
  • atque-corrupti-laboriosam-nobis-explicabo
  • nostrum-ut-vel-voluptates-et
  • quisquam-dolorum-minus-non-ipsam
20 results

README.md

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;