Best Fit algorithm implementation with Binary search Tree

Hey Guys ,
Since last two days , I was busy in an assignment based on the topic of Bin packing problem .
So in this post I am going to explain you about the Bin Packing and Implementing it with best fit algorithm.

So what is actually bin packing ??

It is simply putting a given number of objects into bins of given or maybe variable size so that minimum number of bins are used . It is a real life problem . Bin picking is used various aspects of daily problems.For example suppose there are many number of trucks and ith truck has a capacity of size Mi . Now you have to transport N objects of varying sizes via these trucks . The question is that you have to use minimum number of trucks possible .

If you go through this wikipedia link , you will read that bin packing is a Combinatorial N-P Hard problem . If you aren't familiar with the two big words in the previous line  don't worry , Most of us  too ,aren't familiar with  them . First let me tell you about what does Combinatorial means . It is actually derived from the word Combinatorics  . Combinatorics is a branch of High level Mathematics . In layman terms , the motto of Combinatorics  is to determine how many things are of a kind without actually counting them.

Now what is N-P hard problem ??

It is a very hard term for me  to define . For the layman answer I will post this answer of Quora 

"

To keep things simple, let's just talk about problems with "yes/no" answers.

For some problems we can describe a step-by-step procedure to solve them, and we know that if we use that procedure, it won't take so long that there's no hope of success. For example: "Are there at least ten red houses in your neighborhood?" We can take a walk and count every red house we pass, and eventually we'll either count to ten or walk through the whole neighborhood without seeing ten red houses.

The collection of all of these problems is called "P", and in addition to being able to solve each of them easily enough, we can also fairly easily check the way it was answered. But checking isn't the same as finding an answer -- often it seems easier -- so we have a different name for the group of "problems we can check easily enough", and that name is "NP".

What we don't know is whether being able to check the answer fast enough also means we can find a fast enough way to solve it. Some problems seem harder. For example: "If we only have ten colors to choose from, could we paint everybody's house in the neighborhood so that nobody's house is the same color as any of their friends' houses?" It seems a lot more complicated. The color I choose for my house might wind up deciding the color for somebody on the other side of town whom I've never met. After fifty people have picked their colors, we might find out that there are two friends who'd have to have the same color because of their other friends; then we'd have to back up and start over! But if somebody suggests what colors we should paint everybody's houses, we can still check easily enough to see if their idea works: just go around and ask each person if their house would be the same color as any of their friends' houses.

So we have these hard problems, and we're still not sure if we'll ever find a way to solve them fast enough. This group of hard problems are called "NP-hard". Some are so big and complicated that they're not even in NP: if somebody gives you an answer, you still couldn't come up with a fast enough way to check it. Because we know those are too hard, we use the name "NP-complete" to mean "NP-hard but still in NP", when we want to talk about problems that seem really hard, but aren't so complicated that we couldn't check an answer if we had it.

And the big question nobody has figured out yet is, "Are all the NP-complete problems actually only as hard as the P problems?" (We think they're harder, but we aren't sure.) If you can come up with a good enough way to solve one of those NP-complete problems -- the ones we only know how to check quickly enough -- then you'd become pretty famous for it!"

Moving further towards the problem :

So by now you know that bin packing problem is such that you can't easily check whether the solution is optimum or not .

There are several algorithms which provide a solution for the bin packing .

They are devided in 2 parts :

1. Online Algorithm :

                                 These algorithms are used where items arrive at run time  i.e one at a time . Each item must be put into a bin before considering the next item . These algorithms include : 

a) Next Fit

b) First Fit

c) Best Fit

2.Offline Algorithm : Here we have all the items at once and then we have to find the optimum solution for it . Mainly, First Fit decreasing algorithm is used for these types of problems.

I will be explaining the Online Algorithms in this post .

a) Next Fit :

This algo checks the  every element  before putting them into bins that whether it fits in the same bin as the last item . Uses only if it does not.

 Here is the code below : 

#include <iostream>

using namespace std;

 

// Returns number of bins required using next fit

// online algorithm

int nextFit(int weight[], int n, int c)

{

   // Initialize result (Count of bins) and remaining

   // capacity in current bin.

   int res = 0, bin_rem = c;

 

   // Place items one by one

   for (int i=0; i<n; i++)

   {

       // If this item can't fit in current bin

       if (weight[i] > bin_rem)

       {

          res++;  // Use a new bin

          bin_rem = c - weight[i];

       }

       else

         bin_rem -= weight[i];

   }

   return res;

}

int main()

{

    int weight[] = {2, 5, 4, 7, 1, 3, 8};

    int c = 10;

    int n = sizeof(weight) / sizeof(weight[0]);

    cout << "Number of bins required in Next Fit : "

         << nextFit(weight, n, c);

    return 0;

}

Number of bins required in Next Fit : 4

b) First Fit:
When processing the next item, see if it fits in the same bin as the last item. Start a new bin only if it does not.

#include <iostream> using namespace std;   // Returns number of bins required using first fit // online algorithm int firstFit(int weight[], int n, int c) {     // Initialize result (Count of bins)     int res = 0;       // Create an array to store remaining space in bins     // there can be at most n bins     int bin_rem[n];       // Place items one by one     for (int i=0; i<n; i++)     {         // Find the first bin that can accommodate         // weight[i]         int j;         for (j=0; j<res; j++)         {             if (bin_rem[j] >= weight[i])             {                 bin_rem[j] = bin_rem[j] - weight[i];                 break;             }         }           // If no bin could accommodate weight[i]         if (j==res)         {             bin_rem[res] = c - weight[i];             res++;         }     }     return res; }   // Driver program int main() {     int weight[] = {2, 5, 4, 7, 1, 3, 8};     int c = 10;     int n = sizeof(weight) / sizeof(weight[0]);     cout << "Number of bins required in First Fit : "          << firstFit(weight, n, c);     return 0; }Output:

Number of bins required in First Fit : 4

c) Best Fit:
The idea is to places the next item in the *tightest* spot. That is, put it in the bin so that smallest empty space is left.

// C++ program to find number of bins required using // Best fit algorithm. #include <bits/stdc++.h> using namespace std;   // Returns number of bins required using best fit // online algorithm int bestFit(int weight[], int n, int c) {     // Initialize result (Count of bins)     int res = 0;       // Create an array to store remaining space in bins     // there can be at most n bins     int bin_rem[n];       // Place items one by one     for (int i=0; i<n; i++)     {         // Find the best bin that ca\n accomodate         // weight[i]         int j;           // Initialize minimum space left and index         // of best bin         int min = c+1, bi = 0;           for (j=0; j<res; j++)         {             if (bin_rem[j] >= weight[i] &&                     bin_rem[j] - weight[i] < min)             {                 bi = j;                 min = bin_rem[j] - weight[i];             }         }           // If no bin could accommodate weight[i],         // create a new bin         if (min==c+1)         {             bin_rem[res] = c - weight[i];             res++;         }         else // Assign the item to best bin             bin_rem[bi] -= weight[i];     }     return res; }   // Driver program int main() {     int weight[] = {2, 5, 4, 7, 1, 3, 8};     int c = 10;     int n = sizeof(weight) / sizeof(weight[0]);     cout << "Number of bins required in Best Fit : "          << bestFit(weight, n, c);     return 0; }

Implementing the best fit using a binary search tree gives a proper optimum solution for bin packing .

Below is the code :

#include <iostream>
#include<malloc.h>
using namespace std;

int count =0; // count of the number of bins de leted

int count_of_bins = 0; // it is the count of bins still  present in the Tree and has been used atleast once
// we will use the flag value of each node to alculate count_of_bins

struct node {

int size; // This will store the size of the bins
int flag; // this flag will check whether the bin has been used at least once or not . If used , flag =1 else flag =0
struct node  *left; // pointer to the left node
struct node *right; // pointer to the right node

};


struct node *Create_New_Node(int block_size,int flagval)  // This function will create a new bin of the capacity of the provided size
{

struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->size = block_size ; temp->flag = flagval;
temp->left = temp->right = NULL;

return temp;

}



/* For Inserting a new bin in the tree */
struct node* insert(int block_size,int flag, struct node *Root){

//cout<<flag<<endl;
if(Root==NULL) return Create_New_Node( block_size,flag);
if(block_size<=Root->size)
{
Root->left = insert(block_size,flag,Root->left) ;
}
if(block_size>Root->size)
{
Root->right = insert(block_size,flag,Root->right) ;
}
return Root;

}
/* Searching a particular bin by its size */

struct node* search(struct node* root, int block_size)
{
    // Base Cases: root is null or size is present at root
    if (root == NULL || root->size == block_size)
       return root;
   
    // size is greater than root's size
    if (root->size < block_size)
       return search(root->right, block_size);

    // size is smaller than root's size
    return search(root->left, block_size);
}



/*  For the inorder traversal of the Binary Search Tree */

void inorder(struct node *Root)
{
    if (Root != NULL)
    {
        inorder(Root->left);
        printf("%d ", Root->size);
        inorder(Root->right);
    }
}


void count_of_used_bins(struct node *Root)
{
    if (Root != NULL)
    {
        count_of_used_bins(Root->left);


if(Root->flag==1)
{
//cout<<Root->size<<"  ";
count_of_bins++;
}
     
       count_of_used_bins(Root->right);
    }
}



struct node * minValueNode(struct node* node)
{
    struct node* current = node;

    /* loop down to find the leftmost leaf */
    while (current->left != NULL)
        current = current->left;

    return current;
}

/*  This function deletes the  bin of that particular size
   and returns the new Root */

// to have a better understanding visit : http://quiz.geeksforgeeks.org/binary-search-tree-set-2-delete/
struct node* deleteNode(struct node* Root, int block_size)
{
    // base case
    if (Root == NULL) return Root;

    // If the size to be deleted is smaller than the Root's size,
    // then it lies in left subtree
    if (block_size < Root->size)
        Root->left = deleteNode(Root->left, block_size);

    // If the size to be deleted is greater than the Root's size,
    // then it lies in right subtree
    else if (block_size > Root->size)
        Root->right = deleteNode(Root->right, block_size);

    // if size is same as Root's size, then This is the node
    // to be deleted
    else
    {
        // node with only one child or no child
        if (Root->left == NULL)
        {
            struct node *temp = Root->right;
            free(Root);
            return temp;
        }
        else if (Root->right == NULL)
        {
            struct node *temp = Root->left;
            free(Root);
            return temp;
        }

        // node with two children: Get the inorder successor (smallest
        // in the right subtree)
        struct node* temp = minValueNode(Root->right);

        // Copy the inorder successor's content to this node
        Root->size = temp->size;

        // Delete the inorder successor
        Root->right = deleteNode(Root->right, temp->size);
    }
    return Root;
}


/* This function finds that bin which will have optimum capacity for the required file*/


void findClosestNode(struct node *root, int value, int *min){
    if(!root)
{
  int required_node_size = value + *min;
int size_left = *min;
return ;

}
    int diff = root->size - value;
 
    if((*min > diff)&&(diff>=0)){
        *min = diff;
    }
    /* Case 1 : Look for in left subtree */
 
    if(root->size > value)
        findClosestNode(root->left, value, min);
    else
    /* Case 2 : Look for in right subtree */
        findClosestNode(root->right, value, min);
}
 


int main()
{
int num_of_bins;
cout<<"input the number of bins : ";
cin>>num_of_bins;
cout<<endl;
int num_of_files;
int arr[num_of_bins];
int maxsize = 0; //this will be used to find  the maximum size  available among  the bins
struct node *Root  = NULL;

cout<<"input the size of first bin:  ";
cin>>arr[0]; // creating the Root of the binary search tree
if(arr[0]>maxsize){maxsize = arr[0];}
Root = insert(arr[0],0,Root);
int i;
for(i=1;i<num_of_bins;i++)
{
cout<<"input the size of  bin no .  "<<(i+1)<<": ";
cin>>arr[i];cout<<endl;
if(arr[i]>maxsize){maxsize = arr[i];}
Root = insert(arr[i],0,Root);
}
maxsize = maxsize + 100000 ; //inceasing the max size by 100000
int maxcopy = maxsize;
cout<<"the initial inorder set of bin size is : ";
inorder(Root);cout<<endl;
cout<<"input the number of files : ";
cin>>num_of_files;
cout<<endl;
int barr[num_of_files];



for(i=0;i<num_of_files;i++)
{
maxcopy = maxsize;
cout<<"input the size of  file no .  "<<(i+1)<<": ";
cin>>barr[i];cout<<endl;
findClosestNode(Root,barr[i],&maxcopy);
if(maxcopy!=0)
{
int ans = barr[i] + maxcopy;

Root = deleteNode(Root,ans);
Root = insert(maxcopy,1,Root);
}
if(maxcopy==0){
Root = deleteNode(Root,barr[i]);
count++;
}

}
count_of_used_bins(Root);
cout<<endl;
cout<<"ans is "<<count<<endl;
cout<<"othe one is : "<<count_of_bins<<endl;
cout<<"Number of Bins used are : "<<(count_of_bins + count )<<endl;
cout<<"the final inorder set of bin size is : ";
inorder(Root);cout<<endl;

return 1;
}