Unbounded

Branch and Bound Unbounded Knapsack Java Source Code

Branch and Bound, this is the another way to solve unbounded knapsack problem beside Dynamic Programming Solving like the previous post [Dynamic Programming Unbounded Knapsack]. This way is called Branch and Bound, i’m still confusing with the concepts of this algorithm and how can it solve the problem with optimal result. But for now just forget it and focus on implementating with Java Programming Language.

This algorithm consist of 4 (four) main parts.

  1. Pre Processing :: Sort the items with ascending order by it’s ratio (value/weight)
  2. Initializing :: Take a Greedy Choosing for item 1, then 2, and so on
  3. Reduction Move :: Decrement the least significant digit (most right non-zero)
  4. Expansion Move :: Take a Greedy Choosing for items on right of least significant digit

If you’re still confuse about my explaination, please go to my reference site [BB Unbounded Knapsack]

Okay let’s go to the implementing with source code. First of course declaring the variable…

    private static int   maxWeight = 0; //maximum weight of knapsack
    private static int[] w;             //weight of each item
    private static int[] v;             //value of each item
    private static int[] maxSet;        //set of optimum items
    private static int   maxValue;      //value of maximum set

Then we make the user input getter

    private static boolean getData()
    {
        System.out.print("Input Maximum Knapsack Weight : ");
            maxWeight = new Scanner(System.in).nextInt();

        System.out.print("Input the weight of each item (separate by space) : ");
            String[] temp = new Scanner(System.in).nextLine().split(" ");
            w = new int[temp.length];
            for (int i=0;i<temp.length;i++) w[i] = Integer.valueOf(temp[i]);

        System.out.print("Input the value of each item (separate by space) : ");
            temp = new Scanner(System.in).nextLine().split(" ");
            v = new int[temp.length];
            for (int i=0;i<temp.length;i++) v[i] = Integer.valueOf(temp[i]);

        if (w.length != v.length){
            System.err.println("Number of weight and value data not match!");
            return false;
        }
        return true;
    }

Now, the first step of this algorithm. Pre-Processing

    private static void preProcessing()
    {
        /**
         * Sorting using Selection Sort to Arrange
         * the data by it's ratio (value/weight)
         */
        for (int i=0;i<w.length-1;i++)
        {
            int minIndex = i;
            for (int j=i+1;j<w.length;j++)
            {
                if ((double)v[j]/w[j] < (double)v[minIndex]/w[minIndex])
                {
                    minIndex = j;
                }

            }
            int temp    = w[i];
            w[i]        = w[minIndex];
            w[minIndex] = temp;

            temp        = v[i];
            v[i]        = v[minIndex];
            v[minIndex] = temp;
        }
    }

Then, do the Initializing of item set combination

    private static void initialization()
    {
        /**
         * Make a greedy choosing
         * Take as much as first item, then second then continue...
         */
        int[] combination = new int[w.length];
        for (int i=0;i<w.length;i++)
        {
            int maximum = maxWeight/w[i];
            combination[i] = maximum;
            maxWeight = maxWeight - (maximum*w[i]);
        }

        /**
         * Assume the greedy choice taken is maximum set
         */
        maxSet = new int[combination.length];
        copyAllArrayValueTo(combination, maxSet);

        /**
         * Calculate the value of maximum set taken
         */
        int currentValue = 0;
        for (int i=0;i<maxSet.length;i++)
        {
            currentValue = currentValue + (maxSet[i]*v[i]);
        }
        maxValue = currentValue;
    }

And the final step of algorithm, Reduction and Expansion Move

    private static void reduceAndExpand()
    {
        /**
         * Make a copy of maximum set to be reduced and expanded
         */
        int[] set = new int[maxSet.length];
        copyAllArrayValueTo(maxSet, set);

        /**
         * Reduction and Expansion Step Loop Here
         * Loop until the all of the set is 0
         */
        boolean flag = true;
        while (flag)
        {
            /**
             * Reduction Move
             * Seek the least significant (not zero) digit
             */
            int leastSignificant = set.length-1;
            for (int i=leastSignificant;i>=0;i--)
            {
                if (set[i] != 0)
                {
                    leastSignificant = i;
                    break;
                }
            }

            /**
             * Reduction Move
             * Decrement the least significant digit or
             * set it to 0 (zero) if it's on last position
             */
            if (leastSignificant == set.length-1)
            {
                maxWeight = maxWeight + (set[leastSignificant]*w[leastSignificant]);
                set[leastSignificant] = 0;
            }
            else
            {
                maxWeight = maxWeight + w[leastSignificant];
                set[leastSignificant]--;

                /**
                 * Expansion Move
                 * Take a greedy choosing for items on right of
                 * least significant digit
                 */
                for (int i=leastSignificant+1;i<set.length;i++)
                {
                    int maximum = maxWeight/w[i];
                    set[i] = maximum;
                    maxWeight = maxWeight - (maximum*w[i]);
                }

                /**
                 * Calculating the value of new set
                 */
                int currentValue = 0;
                for (int i=0;i<set.length;i++)
                {
                    currentValue = currentValue + (set[i]*v[i]);
                }

                /**
                 * Replace the optimum set if
                 * the new set better
                 */
                if (currentValue > maxValue)
                {
                    maxValue = currentValue;
                    copyAllArrayValueTo(set, maxSet);
                }

            }

            /**
             * Loop terminator
             * Check if the set is 0
             */
            int itemCount = 0;
            for (int i=0;i<w.length;i++)
            {
                itemCount = itemCount + set[i];
            }
            if (itemCount == 0) flag = false;
        }
    }

Don’t forget the main method and other supporting methods….

    public static void main(String[] args)
    {
        if (!getData()) return;         //getting data from user
        preProcessing();                //ascending sort by ratio
        initialization();               //first greedy choosing
        reduceAndExpand();              //seek for more optimum set

        System.out.println(maxValue);
    }

    private static void copyAllArrayValueTo(int[] source, int[] dest)
    {
        for (int i=0;i<source.length;i++) dest[i] = source[i];
    }

Source and References

  1. University of Melbourne, Australia

Unbounded Knapsack Java Source Code

Hi there, now in this time i’ll try to explain about solving Unbounded Knapsack Problem (UKP) with Dynamic Programming (DP) Method. What is Knapsack Problem? The basic problem is how to choose combination of items from a set of items given to get the maximum value with the knapsack weight or volume restriction. For example, we want to go camping in the mountain, we must bring some stuff like clothes, foods, and drugs. But we just have the limited bag (knapsack) capacity so we must choose the combination of those items which can give us the most benefit.

What’s the different with bounded knapsack? We also call the bounded knapsack with 0-1 knapsack or binary knapsack. Unbounded knapsack is 0-1 knapsack too, but in the UKP we can take more than one items from the same kind. Example, we bring 2 clothes, 5 foods, and 3 drugs. Not in 0-1 knapsack problem, we just can bring 1 items of the same kind.

How the Dynamic Programming Works? The DP method work with the idea “the optimum value of if this item a put on this knapsack is the optimum value of knapsack weight without this item plus value of this item” little confusing? yes i think so. in other word we can say if i reach this weight with this item, then the maximum value is the previous items was added in knapsack plus the new items value. Example : If we want to reach knapsack weight 5 with adding items with weight 2 then the optimum value is : “the optimum value of knapsack with weight 3 plus the value of item with weight 2”.

f(s) = Value(i) + f(s – Weight(i))

So, we can arrange the dynamic table increasingly from most lightweight knapsack optimum value. from weight=0 which must be 0 (zero) valued because nothing can get in on that knapsack capacity, until knapsack weight=maximumweight. With this method we never calculate again the optimum value of previous knapsack before which needed to calculate the present optimum value.

Okay the implementation, first we need some variables and arrays to store the information

    private static int   maxWeight = 0; //maximum weight of knapsack
    private static int[] w;             //weight of each item
    private static int[] v;             //value of each item
    private static int[] a;             //maximum value each knapsack
    private static int[] l;             //last item added each knapsack

And of course getting the user input

    private static boolean getData(){
        System.out.print("Input Maximum Knapsack Weight : ");
            maxWeight = new Scanner(System.in).nextInt();

        System.out.print("Input the weight of each item (separate by space) : ");
            String[] temp = new Scanner(System.in).nextLine().split(" ");
            w = new int[temp.length];
            for (int i=0;i<temp.length;i++) w[i] = Integer.valueOf(temp[i]);

        System.out.print("Input the value of each item (separate by space) : ");
            temp = new Scanner(System.in).nextLine().split(" ");
            v = new int[temp.length];
            for (int i=0;i<temp.length;i++) v[i] = Integer.valueOf(temp[i]);

        if (w.length != v.length){
            System.err.println("Number of weight and value data not match!");
            return false;
        }
        return true;
    }

Then we can get in to the method, the unbounded knapsack

    private static void fillUnboundedKnapsack()
    {
        int   n = w.length;         //number of items

        /**
         * Initializing table
         * table a with default value =  0
         * table l with default value = -1
         */
        a = new int[maxWeight+1];
        l = new int[maxWeight+1];

        setAllArrayValueTo(a,  0);
        setAllArrayValueTo(l, -1);

        /**
         * Unbounded Knapsack Step
         */
        for (int i=1;i<a.length;i++)
        {
            for (int j=0;j<n;j++)
            {
                if (w[j] <= i &&
                        (v[j] + a[i - w[j]]) > a[i])
                {
                    a[i] = v[j] + a[i - w[j]];
                    l[i] = j;
                }
            }
        }
    }

How can we know the items combination from only the sequence code above? Check this out…

    private static int[] trackCombination()
    {
        int[] combination = new int[w.length];

        int postTracker = l.length-1;
        int itemTracker = l[postTracker];

        /**
         * Tracking back the combination
         */
        while (itemTracker != -1 && postTracker > 0)
        {
            combination[itemTracker]++;
            postTracker = postTracker - w[itemTracker];
            itemTracker = l[postTracker];
        }

        return combination;
    }

And finally the main method which cover it all….

    public static void main(String[] args)
    {
        if (!getData()) return;             //getting data from user
        fillUnboundedKnapsack();            //run the algorithm
        int[] optimal = trackCombination(); //seek for items combination

        /* Just an Output Step */
        System.out.println("Maximum Value : " + a[a.length-1]);
        System.out.print("Combination : ");
        for (int i=0;i<optimal.length;i++){
            System.out.print(optimal[i] + " ");
        }
        System.out.println();
    }

Almost forgot… maybe you ask about the setAllArrayValueTo() method, it just a complementary method to set all array values to the second parameter. The code just like..

    private static void setAllArrayValueTo(int[] array, int value){
        for (int i=0;i<array.length;i++) array[i] = value;
    }