Implementation of 0/1 Knapsack problem using Dynamic Programming in Java

What is 0/1 Knapsack problem ?The knapsack or rucksack problem is a problem in combinatorial optimization. Here there are a set of items(n) which has a profit value(v) and weight(w). 

There is a bag which has a maximum capacity(W). Now the problem is to fill the bag with the following restrictions :   1. You can either choose an item completely or reject it. (0 or 1)   2. The total weight of bag must not exceed its maximum capacity W. i.e. (Sum of w[i]) <= W   3.  The total value or profit of items chosen must be maximum. i.e. Sum of p[i] is maximumwhere 0 <  i <=n.

How to solve 0/1 Knapsack problem in Java ?Step1: Structure: Characterize the structure of an optimal solution.    – Decompose the problem into smaller problems, and find a relation between the structure of the optimal solution of the original problem and the solutions of the smaller problems.
Step2: Principle of Optimality: Recursively define the value of an optimal solution.    – Express the solution of the original problem in terms of optimal solutions for smaller problems.Step 3: Bottom-up computation: Compute the value of an optimal solution in a bottom-up fashion by using a table structure.
Step 4: Construction of optimal solution: Construct an optimal solution from computed information.

import java.util.Scanner;

 

public class Knapsack {

  

 private int n,W;  //number of items and maximum capacity

 private int w[],v[];  //weights and values of items

 private int V[][];  //table to store results of sub-problems

  

 /**

  * Takes necessary inputs and initializes for solving

  */

 private void initialize(){

  Scanner sc = new Scanner(System.in);

  System.out.print("Enter number of items : ");

  n = sc.nextInt();  //number of items

  System.out.print("Enter W of knapsack : ");

  W = sc.nextInt();  //capacity of knapsack

  w = new int[n];

  v = new int[n];

  System.out.println("Enter ws and vs of items : ");

  for(int i = 0; i < n; i++){

   w[i] = sc.nextInt();  //weight of item

   v[i] = sc.nextInt();  //profit of item

  }

  V = new int[n+1][W+1];  //initializing the table to hold results

  for(int i = 0; i <= W; i++) V[0][i] = 0;

 }

  

 /**

  * Computes the result

  */

 public void knapsack(){

  //table for backtracking to get the items chosen

  int x[][] = new int[n+1][W+1];

  //filling tables

  for(int i = 1; i <= n; i++)

   for(int j = 0; j <= W; j++)

    if((w[i-1] <= j) && (v[i-1]+V[i-1][j-w[i-1]] > V[i-1][j])){

     V[i][j] = v[i-1] + V[i-1][j-w[i-1]];

     x[i][j] = 1;

    }

    else{

     V[i][j] = V[i-1][j];

     x[i][j] = 0;

    }

  //backtracking

  System.out.printf("Items Chosen\n%5s%7s%7s\n", "Item","Weight","Profit");

  int K = W;

  for(int i = n; i >= 1; i--)

   if(x[i][K] == 1){

    System.out.printf("%5d%7d%7d\n",i,w[i-1],v[i-1]);

    K -= w[i-1];

   }

  System.out.println("Maximum profit : "+V[n][W]);

 }

  

 public static void main(String[] args) {

  Knapsack obj = new Knapsack();

  obj.initialize();

  obj.knapsack();

 }

}