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

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;
    }