Select Git revision
start_config_editor
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;