0
$\begingroup$

Suppose we have $n$ objects with weights $w_i \in (0,1]$ and we must insert them into bins with the constraint that every bin must contain objects which weight less than $1 \, kg$.

The first-fit algorithm must: examine the objects with the order they're given $(w_1, w_2, \dots , w_n)$ and insert them into the bins, satisfying the above constraint. It must run in $O(n \log n)$ time, returning the number of bins which were used and which objects were inserted in each bin.

I've constructed an algorithm, using Hash Tables, where the objects' numbers are the keys and the bins' numbers are the values and it basically does this:

for(int i = 0; i < n; i++){
    sum = sum + w[i];

    if(sum < noOfBins){
        BinContent.put(i + 1, noOfBins);
    }

    else {
        noOfBins++;
        BinContent.put(i + 1, noOfBins);
    }

and then it prints noOfBins and BinContent, but I believe this algorithm is $O(n)$ and the proper way would be to use Binary Trees instead of Hash Tables.

Is the complexity of the given algorithm $O(n)$? If so, could you give me a hint on how to achieve $O(n \log n)$ time complexity?

$\endgroup$
  • 1
    $\begingroup$ Your current algorithm is incorrect: if sum<nOfBins, it could still be nessecary to pick a new bin. For example, take the weights $(0.7,0.5,0.6)$. When inserting $0.6$, the total sum is $1.8<2$, but we still need at least 3 bins. You will have to do some form of 'searching' for the right bin to insert, which is where the extra log factor will come from. $\endgroup$ – Discrete lizard May 2 '19 at 9:07
  • $\begingroup$ What's the target of your problem? Minimize the number of bins? Also, do you mean the objects arrive in an online fashion, and when an object arrives, the algorithm must determine immediately into which bin to insert it? $\endgroup$ – xskxzr May 2 '19 at 9:13
  • $\begingroup$ The problem is implementing “first fit” in O(n log n). $\endgroup$ – gnasher729 May 2 '19 at 10:10
1
$\begingroup$

Your solution has $O(n)$ computational complexity but it doesn't implement the first fit algorithm. The thought behind your solution is to insert the items one by one in the given order (that's correct) and to insert the current item in the last bin if it fits in it or to create a new bin if the current item doesn't fit in the current bin (that's wrong).

First of all, this is not what first fit algorithm asks for. You have to insert the current item in the first used bin that it fits in and if it doesn't fit in any already used bin then you will have to use a new one. You shouldn't consider only the last used bin for the insertion, but all the existing bins, that's my point. Additionally as Discrete lizard mentions in his comment, your implementation is wrong even under the wrong perspective.

I will present the correct first fit method using two different algorithms. The first one is sub-optimal, a brute force with $O(n^2)$ computational complexity, because such an algorithm will illustrate better the first fit logic. The second algorithm is the optimal one with $O(nlogn)$ computational complexity.

Now let's consider the first algorithm. We will initially use no bin. As we read the size of each item we will just iterate from left to right over all the already used bins. If we meet a bin where the current item fits (its empty size is at least equal to the size of the current item) then we use this bin, otherwise we have to use a new bin. Note that it will be very helpfull to save the remaining size of each bin and make an update every time a new item is inserted. Bellow I implement this simple solution using C++.

#include <iostream>
#include <vector>
#include <list>
using namespace std;

int n = 0;  // Current number of items

int b = 0;  // Current number of bins

vector<int> IBM;  // Item->bin matching: IBM[i] = bin of i-th item
vector<list<int>> BIM;  // Bin->item matching: BIM[i] = list of items in i-th bin

vector<double> RBS;  // Remaining bin space: RBS[i] = remaining space of i-th bin

int main()
{
    double item_size;  // Current item size
    while (cin >> item_size)  // While there are still items put them in bins
    {
        bool used_bin_used = false;  // Was the current item put in an already used bin?
        for (int i = 0; i < b; i++)  // Iterate over already used bins from left to right
        {
            if (RBS[i] >= item_size)  // If i-th bin has enough space for the current item...
            {
                IBM.push_back(i);  // Current item was put in i-th bin
                BIM[i].push_back(n);  // i-th bin contains the current item
                RBS[i] -= item_size;  // Decrease the available space of the i-th bin
                used_bin_used = true;  // The current item put in an already used bin
                break;  // No more search for current item
            }
        }
        if (!used_bin_used)  // If true, not new bin for current item
        {
            IBM.push_back(b);  // Current item was put in new bin
            list<int> tmp;  // Helping temporary list
            tmp.push_back(n);
            BIM.push_back(tmp);  // The new bin contains the current item
            RBS.push_back(1 - item_size);  // Save the remaining space of the current bin
            b++;  // Increased number of used bins
        }
        // Output current result using numbering starting from 1
        cout << "Item with id = #" << n + 1 << " was put in bin with id = #" << IBM[n] + 1 << ".\n" << flush;
        n++;  // Increased number of items
    }
    // Output bin containing info
    cout << n << " items were inserted in " << b << " bins.\n";
    for (int i = 0; i < b; i++)
    {
        cout << "Bin #" << i + 1 << " contains items: ";
        for (list<int>::iterator it = BIM[i].begin(); it != BIM[i].end(); it++)
        {
            cout << *it + 1 << ' ';
        }
        cout << '\n';
    }
    return(0);
}

Notice that the solution above follows the online fashion. For each of the $n$ items we search linerly $O(n)$ bins in the worst case, so the computational complexity of the above algorithm is $O(n^2)$.

Now let's construct a second, better algorithm. We want to improve the computational complexity of the above algorithm. We would like to reduce the time needed to find the first (leftmost) bin where the current item can fit, which required $O(n)$ time per item. To achieve this goal we can use a segment tree for maximum range queries on the remaining bin spaces. This way every time time a new item is given we can go down the segment tree and find the bin that we should use in $O(logn)$ time for each item. So the computatonal complexity of the algorithm drops down to $O(nlogn)$. We can even follow the online fashion and not require any knowledge about the value $n$, as we did in the previous implementation by doubling the size of the segment tree used every time we have an overflow. The computational complexity will remain $O(nlogn)$ which can be proved using amortized analysis. The C++ implementation of this algorithm is given bellow.

#include <iostream>
#include <vector>
#include <list>
using namespace std;

int n = 0;  // Current number of items

int b = 0;  // Current number of bins

vector<int> IBM;  // Item->bin matching: IBM[i] = bin of i-th item
vector<list<int>> BIM;  // Bin->item matching: BIM[i] = list of items in i-th bin

vector<double> RBS;  // Remaining bin space: RBS[i] = remaining space of i-th bin

vector<double> A;  // Vector with bin remaning sizes used by segment tree

vector<double> tree;  // Vector with segment tree's values

void make_base(int L)
{
    for (int i = A.size(); i < L; i++)
    {
        A.push_back(1);  // New bins will be empty
    }
    for (int i = tree.size(); i < 4 * L + 5; i++)
    {
        tree.push_back(1);  // These values will be overwritten by build
    }
}

void build(int node, int start, int end)
{
    if (start == end)
    {
        tree[node] = A[start];
    }
    else
    {
        int mid = (start + end) / 2;
        build(2 * node + 1, start, mid);
        build(2 * node + 2, mid + 1, end);
        tree[node] = max(tree[2 * node + 1], tree[2 * node + 2]);
    }
}

void update(int node, int start, int end, int idx, double val)
{
    if(start == end)
    {
        A[idx] = tree[node] = val;
    }
    else
    {
        int mid = (start + end) / 2;
        if(start <= idx && idx <= mid)
        {
            update(2 * node + 1, start, mid, idx, val);
        }
        else
        {
            update(2 * node + 2, mid + 1, end, idx, val);
        }
        tree[node] = max(tree[2 * node + 1], tree[2 * node + 2]);
    }
}

int query(int node, int start, int end, double val)
{
    if (start == end)
    {
        return(start);
    }
    int mid = (start + end) / 2;
    if (tree[2 * node + 1] >= val)
    {
        return(query(2 * node + 1, start, mid, val));
    }
    return(query(2 * node + 2, mid + 1, end, val));
}

int main()
{
    double item_size;  // Current item size
    while (cin >> item_size)  // While there are still items put them in bins
    {
        if (tree.empty() || tree[0] < item_size)
        {
            int L;
            if (A.empty()) L = 1;
            else L = 2 * A.size();
            make_base(L);
            build(0, 0, A.size() - 1);
        }
        int idx = query(0, 0, A.size() - 1, item_size);
        if (idx < b)
        {
            IBM.push_back(idx);  // Current item was put in idx-th bin
            BIM[idx].push_back(n);  // idx-th bin contains the current item
            RBS[idx] -= item_size;  // Decrease the free space of idx-th bin
            update(0, 0, A.size() - 1, idx, RBS[idx]);  // Update segment tree
        }
        else
        {
            IBM.push_back(b);  // Current item was put in new bin
            list<int> tmp;  // Helping temporary list
            tmp.push_back(n);
            BIM.push_back(tmp);  // The new bin contains the current item
            RBS.push_back(1 - item_size);  // Save the remaining space of the current bin
            update(0, 0, A.size() - 1, idx, RBS[idx]);  // Update segment tree
            b++;  // Increased number of used bins
        }
        // Output current result using numbering starting from 1
        cout << "Item with id = #" << n + 1 << " was put in bin with id = #" << IBM[n] + 1 << ".\n" << flush;
        n++;  // Increased number of items
    }
    // Output bin containing info
    cout << n << " items were inserted in " << b << " bins.\n";
    for (int i = 0; i < b; i++)
    {
        cout << "Bin #" << i + 1 << " contains items: ";
        for (list<int>::iterator it = BIM[i].begin(); it != BIM[i].end(); it++)
        {
            cout << *it + 1 << ' ';
        }
        cout << '\n';
    }
    return(0);
}

Finally I would like to mention that first fit is a method that doesn't minimize the number of bins used. Solving this problem optimally is NP-hard. First fit algorithm is just a method that usually provides an acceptable solution in a fast manner. It is often used in practice when speed is preffered over optimallity.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.