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

I have used your code for my case to find the best basket of products by consumers. It was very helpful and thanks a lot.

Omid

Hi!

many thanks for your nice code. But unfortunately it doesn’t work correctly – this code can’t find ALL combinations and result DEPENDS from elements position in input array.

As example you may test code with input maximum weight as 71, weight array {45,23,21,27} and value array {1, 1, 1, 1}. Your code will return result array {0, 3, 0, 0} = 69 instead of more precise {0, 1, 1, 1} = 71.

Now I simply make loop with cyclic array shifting and run code again, but this also DOESN’T guarantee that all combinations will be found. And after each array shifting I receive new result.

My modification you may see here

https://bitbucket.org/YuriBtr/unbounded-knapsack-task

Hi, I do not understand the fillUnboundedKnapsack() method and trackCombination method().

Can you please elaborate what are we doing at each step?

Also how to get know about which items got selected and the count the each item selected?