I Made Krisna's Times My Way to Write the Times

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