0-1 Knapsack problem in Java

In this tutorial, you will learn about the 0-1 Knapsack problem in Java. But before that, you should have a theoretical knowledge of the 0-1 Knapsack problem. So, what does the word Knapsack mean? Knapsack means a simple bag of fixed capacity. And in the 0-1 knapsack problem, you need to simplify and calculate the maximum weight to get maximum profit. It has a great application in our day to day life. For instance, the amount of investment to make in shares with an amount. The code discussed here is by use of dynamic programming.

Java Code For 0-1 Knapsack Problem

Now let’s discuss its code.

package knapsack;
import java.io.*;
public class Knapsack {
public static void main(String[] args) {
int p[] = {0,1,2,5,6};
int wt[] = {0,2,3,4,5};
int m=8,n=4,i,j,l,p1,q;
int k[][]=new int[5][9];

In this part of code, the array “p” is for profits, array “wt” is for weights.
“m” is the maximum capacity of bag i.e. declared as 8.
“n” is the number of weights i.e. 4.
and array k[][] is to store values in a table as we do in Knapsack Problem.

for(i=0;i<=n;i++)
       {
           for(j=0;j<=m;j++)
           {
               if(i==0||j==0)
                   k[i][j]=0;
               else if(wt[i]<=j)
                   k[i][j] = Math.max(p[i]+k[i-1][j-wt[i]],k[i-1][j]); 
             else
                   k[i][j] = k[i-1][j]; 
               System.out.print(" | "+k[i][j]);
         } 
           System.out.println();
      }

In this part, the loop is to travel through the table as we do in the 0-1 Knapsack algorithm and fill the values accordingly.

p1=n;q=m;
      while(p1>0&&q>0)
      {
          if(k[p1][q]==k[p1-1][q])
          {
              System.out.println(p1+"=0");p1--;
          }
          else
          {
              System.out.println(p1+"=1");p1--;q=q-wt[p1];
          }
      }
          
                     }
      }

Using this part of the code, we find out which weight gets to go inside the bag and which does not. The weight going inside the bag is represented by 1 and the one not by 0.

Output:-

| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1
| 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3
| 0 | 0 | 1 | 2 | 5 | 5 | 6 | 7 | 7
| 0 | 0 | 1 | 2 | 5 | 6 | 6 | 7 | 8
4=1
3=1
2=0
1=0

Also read: Job Sequencing Problem using Greedy method in Java

Leave a Reply

Your email address will not be published. Required fields are marked *