Bin packing: Example Code (Java)

In this post I will present example code for solving the Bin Packing Problem. I will not go into what exactly Bin Packing is, as there are enough websites that do a good job describing it. As always, wikipedia is a good start to get a general overview: Wikipedia Bin Packing Problem.

Bin Packing: Brute Force Solution

To check all possible solutions for the bin packaging problem (brute force), a recursive approach can be used: Iterate over all bins, try to put the current item in the bin and – if it fits – call the same method with the next item.

    /**
     * bruteforce solution to bin packing problem.
     *
     * @param in list of items to be packed
     * @param currentPosition position in input list
     */

    private void bruteforce(List<Integer> in, int currentPosition) {
        if (currentPosition >= in.size()) { // reached last item, done with this iteration
            int filledBins = getFilledBinsCount();
            if (filledBins < currentBestSolution) { // is this solution better than the current best?
                currentBestSolution = filledBins; // then save it
                currentBestBins = deepCopy(bins);
            }
            return;
        }
        // iterate over bins
        Integer currentItem = in.get(currentPosition);
        for (Bin bin : bins) {
            if (bin.put(currentItem)) {
                bruteforce(in, currentPosition + 1);
                bin.remove(currentItem);
            } // else: item did not fit in bin, ignore
        }
    }

First Fit Decreasing Algorithm

Implementing the first fit decreasing algorithm is quite simple. Just sort your input (descending), and then iterate over your input, packing each item into the first bin it fits into.

    /**
     * first fit decreasing solution for bin packing problem
     */

    public int firstFitDecreasing() {
        Collections.sort(in, Collections.reverseOrder()); // sort input by size (big to small)
        bins.add(new Bin(binSize)); // add first bin
        for (Integer currentItem : in) {
            // iterate over bins and try to put the item into the first one it fits into
            boolean putItem = false; // did we put the item in a bin?
            int currentBin = 0;
            while (!putItem) {
                if (currentBin == bins.size()) {
                    // item did not fit in last bin. put it in a new bin
                    Bin newBin = new Bin(binSize);
                    newBin.put(currentItem);
                    bins.add(newBin);
                    putItem = true;
                } else if (bins.get(currentBin).put(currentItem)) {
                    // item fit in bin
                    putItem = true;
                } else {
                    // try next bin
                    currentBin++;
                }
            }
        }
        return bins.size();
    }

Download Source Code for Bin Packing Problem

Java Bin Packing Source Code [3.9 kB]

Linux Mint: Remove PPA

Linux Mint does not provide the option to remove a ppa.

If you try it, this will be the result:

sudo add-apt-repository --remove ppa:somePPA/ppa
Usage: add-apt-repository [options] repository

add-apt-repository: error: no such option: --remove

But you can still manually remove a ppa in Linux Mint by removing the file that defines it. All ppa are defined in /etc/apt/sources.list.d . So you can do the following:

# find the correct ppa file to delete by listing all ppa files:
ls /etc/apt/sources.list.d

# delete the ppa that you would like to remove:
sudo rm /etc/apt/sources.list.d/some-ppa-to-remove.list

# update
sudo apt-get update

And that is it, you should now have removed the ppa.

Comparison of Free UML Tools

There is a lot of different UML modelling software to choose from. Here, I will create a short overview over the most common free uml tools. This list is not meant as an exaustive review, but more to give you an idea what each of the tools can to so you have an easier time choosing the uml tool that is best for you.

Continue

Linux: Installing Ruby on Rails

The official Ruby on Rails documentation has a good guide on how to install Ruby on Rails. I still had some problems setting everything up, so here I will describe how I installed Ruby on Rails on Linux (LMDE).

Installing Ruby on Linux

Before installing Ruby on Rails we need to install Ruby as well as Ruby Gems and sqlite:

sudo apt-get install ruby rubygems sqlite3

Installing Ruby on Rails on Linux

sudo gem install rails -V

-V because otherwise you will get no direct feedback. Downloading and installing Ruby on Rails takes a lot of time, so without verbose output it looks like the install of ruby on rails stopped.

If the installation hangs at this step:

Installing RDoc documentation for rails-4.1.0...
rdoc --op /var/lib/gems/1.9.1/doc/rails-4.1.0/rdoc lib --title rails-4.1.0 Documentation --quiet

Try to install Ruby on Rails without documentation:

sudo gem install rails -V --no-ri --no-rdoc

Installing Ruby on Rails on LMDE (Linux Mint Debian Edition)

On LMDE, the above steps did not work for me, I got the following error message:

ERROR:  Error installing rails:
    ERROR: Failed to build gem native extension.

        /usr/bin/ruby1.9.1 extconf.rb
/usr/lib/ruby/1.9.1/rubygems/custom_require.rb:36:in `require': cannot load such file -- mkmf (LoadError)
    from /usr/lib/ruby/1.9.1/rubygems/custom_require.rb:36:in `require'

    from extconf.rb:1:in `<main>'

This could be fixed by installing the following package before installing Ruby on Rails:

sudo apt-get install ruby-dev

Installing additional dependencies for Ruby on Rails

The Ruby on Rails server does not work without a Javascript Runtime (You would get the following error when starting the server: Could not find a JavaScript runtime.). You can install execjs with this command:

sudo gem install execjs

execjs depends on nodejs, so go ahead and install that as well:

sudo apt-get install nodejs

Creating a new Rails Project and starting the Server

Now you can go ahead and check if everything works:

rails new TestProject
cd TestProject
rails server
If you now visit http://localhost:3000/ you should see a page displaying: Welcome aboard You’re riding Ruby on Rails!

Installing QGIS on LMDE (Linux Mint Debian Edition)

The solution that I found for installing qgis (Quantum GIS) on LMDE (Linux Mint Debian Edition) is not optimal, but the only one that worked for me.

I am getting QGIS directly from the QGIS Debian repository and I am temporarily adding the main debian repository to my sources, because QGIS depends on some packages that are not included in LMDE.

LMDE: Install QGIS

1. Add QGIS to your sources.lst:

sudo vim /etc/apt/sources.list
# add:
deb http://qgis.org/debian/ jessie main
deb http://ftp.us.debian.org/debian/ jessie main

After this, do not call apt-get upgrade until you removed these lines.

2. Now you can install QGIS:

sudo apt-get update
sudo apt-get install qgis

3. And at last remove the added lines from your sources.lst.

sudo vim /etc/apt/sources.list
# remove:
deb http://qgis.org/debian/ jessie main
deb http://ftp.us.debian.org/debian/ jessie main

sudo apt-get update

This step is important, as otherwise a call to apt-get upgrade could break your system.

That’s it, now QGIS should run on your installation of LMDE.