Computer Science 225
Advanced Programming

Spring 2017, Siena College

Home     Syllabus     Schedule     Examples

BinPacking BlueJ Project

Click here to download a BlueJ project for BinPacking.

BinPacking Source Code

The Java source code for BinPacking is below. Click on a file name to download it.

BinPacking.java

import java.util.ArrayList;
import java.util.Scanner;

/**
 * Example BinPacking: Bin packing demonstration of recursion.
 *
 * @author Jim Teresco, Siena College, Computer Science 225, Spring 2017
 *
 */

public class BinPacking {

    /**
     * recursive method to try to do bin packing on the given items in a given size bin
     * 
     * @param items the ArrayList of item sizes
     * @param size the size of the bin to fit
     * 
     * @return an ArrayList of item sizes to include in solution, or null if no solution
     */
    public static ArrayList<Integer> binPack(ArrayList<Integer> items, int size) {

        // base case: 0 size (we'll fill with items as we back out of the recursion)
        if (size == 0) {
            return new ArrayList<Integer>();
        }
        
        // general case: we need to add something, so let's try each item that fits, and we're done
        // if we find any solutions
        for (int itemNum = 0; itemNum < items.size(); itemNum++) {
            int item = items.get(itemNum);
            if (item <= size) {
                // it's a candidate, so let's attempt
                items.remove(itemNum); // will remove by position
                ArrayList<Integer> answer = binPack(items, size - item);
                items.add(itemNum, item); // put it back for future loop iterations
                // did we find an answer?
                if (answer != null) {
                    answer.add(item);
                    return answer;
                }
            }
        }
        // no solutions found using any of the items, so we return null to indicate failure
        return null;
        
    }
    
    /**
     * main method to run an instance of the bin packing problem
     * 
     * @param args not used
     */
    public static void main(String[] args) {
        
        // storage for our target bin size and list of items to pack therein
        int binSize;
        ArrayList<Integer> items = new ArrayList<>();
        
        Scanner keyboard = new Scanner(System.in);
        
        // some better error checking here would be good
        System.out.print("How large is your bin? ");
        binSize = keyboard.nextInt();
        
        System.out.println("Enter the sizes of items, 0 to end.");
        int nextItem = keyboard.nextInt();
        while (nextItem != 0) {
            items.add(nextItem);
            nextItem = keyboard.nextInt();
        }
            
        // call the recursive method to get started
        ArrayList<Integer> answer = binPack(items, binSize);
        
        // report result
        if (answer == null) {
            System.out.println("No solution.");
        }
        else {
            System.out.println("Take items of sizes: " + answer);
        }
    
    }
}