Knapsack problem in Java

We have a collection of items in the knapsack problem. Every object has a weight and a value. These things should go in a knapsack. But there is a weight restriction. As a result, we must select objects whose combined weight does not go over the allowed limit and whose combined value is as high as possible.

There are various solutions to the knapsack conundrum.

0/1 Knapsack issue

The weights and values of n different things are provided. To have the most value, these things must be placed inside a backpack with capacity k. Additionally, the knapsack's capacity k must not be exceeded by the combined weight of all the goods inside.

Exhaustive search approach

The brute force method is used in the exhaustive search Each set of items is tested in this method, and the value is calculated for each set. The solution is the set that produces the highest value.

Program for 0/1 Knapsack problem in Java

Knapsack.java

//  Exhaustive search approach for  0 - 1 Knapsack problem   
// A exhaustive search approach for the 0 - 1 Knapsack problem   
public class Knapsack 
{  
  // a method with name max is declared to find the maximum value between 2 numbers x and y
public int max(int x, int y)  
{  
// returns the maximum value
return (x > y ) ? x : y;  
}  
// Selecting the object to get maximum profit and  to fit in the bag of capacity k
public int knapSackVal(int k, int w[], int v[], int l)  
{  
// Checking whether the bag is empty 
if (l == 0 || k == 0)  
{  
    return 0;  
}  
if (w[l - 1] > k)  
{  
// usinf recursion to get maximum value
return knapSackVal(k, w, v, l - 1);  
}  
else  
{  
int v1 = knapSackVal(k - w[l - 1], w, v, l - 1);  
int v2 = knapSackVal(k, w, v, l - 1);  
return max(v[l - 1] + v1, v2);  
}  
}  
// Main method at which point of execution starts 
public static void main( String args [ ] )  
{  
 // Declaring the values of objects
int values_of_objects[] = new int [ ] { 150 , 20 , 30 } ;  
// Declaring the weights of objects
int weights_of_objects[] = new int [ ] { 30 , 20 , 40 } ;  
  
int k = 70;  
int l = values_of_objects . length ;  
Knapsack o1 = new Knapsack ( ) ;  
int ans = o1.knapSackVal ( k , weights_of_objects ,  values_of_objects , l ) ;  
System . out . println ( " The maximum value is :  "  +  ans ) ;  
}  
}  

Output

Using Dynamic Programming

Dynamic programming became necessary due to how long the method above took to produce the desired outcome. The approach above so fails over time.Program for 0/1 knapsack problem using dynamic programming

 KnapsackExample.java

public class KnapsackExample 
{  
// A maximum method, which returns  the maximum of two integers num1 and num2  
public int max(int num1, int num2)  
{  
    return (num1 > num2) ? num1 : num2;  
}  
public int max_value_knapsack(int C1, int w1[], int value[], int l1)  
{  
int j1, wt1;  
int dp1[][] = new int[l1 + 1][C1 + 1];  
for (j1 = 0; j1 <= l1; j1++)  
{  
for (wt1 = 0; wt1 <= C1; wt1++)  
{  
if (j1 == 0 || wt1 == 0)  
{  
    // base case  
    dp1[j1][wt1] = 0;  
}  
else if (w1[j1 - 1] <= wt1)  
{  
    dp1[j1][wt1] = max(value[j1 - 1] + dp1[j1 - 1][wt1 - w1[j1 - 1]], dp1[j1 - 1][wt1]);  
}  
else  
{  
    dp1[j1][wt1] = dp1[j1 - 1][wt1];  
}  
}  
}  
return dp1[j1 - 1][C1];  
}  
//  Main method  
public static void main(String argvs[])  
{  
// input arrays  
// Declaring the values of objects
int ValuesOfObjects[] = new int [ ] { 200 , 150 , 100 } ;  
// Declaring the weights of objects
int WeightsOfObjects[] = new int [ ] { 130 , 20 , 40 } ;  


int C1 = 50;  
// length of the input arrays  
int l1 = ValuesOfObjects.length;  
// instantiating the class KnapsackExample  
KnapsackExample o2 = new KnapsackExample();  
// invoking the method maxValueKnapsack()  
int max_value = o2.max_value_knapsack(C1, WeightsOfObjects, ValuesOfObjects, l1);  
// displaying the final result  
System.out.println("The maximum value is: " + max_value);  
}  
}

Output