Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • 0/1 Knapsack Solution in Java

    • 0
    • 1
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 880
    Comment on it

    Hi, this blog is to help you to know about 0/1 knapsack problem and how to solve it using Java.

     

    Problem Definition

    Suppose there is a thief who came to steal thing from someone's home. He has a knapsack(shoulder bag) with him with a limit of weight it can carry. So thief wants to maximize his profit by only keeping the things which have more values and also wants to utilize his knapsack efficiently. He is not allowed to break any item i.e. he has to pick any item or he should not pick that item.


    For example
    Lets say there are three things can be taken by the thief and their weight are 10, 20 and 30 respectively. The value of these elements are 60, 100 and 120 respectively.

     

     

    The weight capacity of bag is 50. Now the options with thief are to pick 

    10 weight item resulting a total weight of 10 and profit of 60 

    20 weight item resulting a total weight of 20 and profit of 100 

    30 weight item resulting a total weight of 30 and profit of 120 

    10, 20 weight items resulting a total weight of 30 and profit of 60 + 100 = 160

    10, 30 weight items resulting a total weight of 40 and profit of 60 + 120 =  180

    20, 30 weight items resulting a total weight of 50 and profit of 100 + 120 = 220

    so the item with weight 20 and 30 should be picked to maximize his profit.

    Suppose now the weight capacity of the knapsack is reduced to 30, then he should choose 10, 20 weight items instead of 30 as profit is 160 in this case. 

     

    Here is a dynamic programming approach to solve the above problem

    package com.tech.blog;
    
    import java.util.Scanner;
    
    public class ZeroOneKnapsack {
    
    	public void solve(int[] wt, int[] val, int W, int N) {
    		int NEGATIVE_INFINITY = Integer.MIN_VALUE;
    		int[][] m = new int[N + 1][W + 1];
    		int[][] sol = new int[N + 1][W + 1];
    		for (int i = 1; i <= N; i++) {
    			for (int j = 0; j <= W; j++) {
    				int m1 = m[i - 1][j];
    				int m2 = NEGATIVE_INFINITY;
    				if (j >= wt[i])
    					m2 = m[i - 1][j - wt[i]] + val[i];
    				m[i][j] = Math.max(m1, m2);
    				sol[i][j] = m2 > m1 ? 1 : 0;
    			}
    		}
    		int[] selected = new int[N + 1];
    		for (int n = N, w = W; n > 0; n--) {
    			if (sol[n][w] != 0) {
    				selected[n] = 1;
    				w = w - wt[n];
    			} else
    				selected[n] = 0;
    		}
    		System.out.print("\nItems with weight ");
    		for (int i = 1; i < N + 1; i++)
    			if (selected[i] == 1)
    				System.out.print(wt[i] + " ");
    		System.out.println("are selected by knapsack algorithm.");
    	}
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		ZeroOneKnapsack zeroOneKP = new ZeroOneKnapsack();
    
    		System.out.println("Enter number of elements ");
    		int n = sc.nextInt();
    
    		int[] wt = new int[n + 1];
    		int[] val = new int[n + 1];
    
    		System.out.println("Enter weight for " + n + " elements");
    		for (int i = 1; i <= n; i++)
    			wt[i] = sc.nextInt();
    		System.out.println("Enter value for " + n + " elements");
    		for (int i = 1; i <= n; i++)
    			val[i] = sc.nextInt();
    
    		System.out.println("Enter knapsack weight ");
    		int W = sc.nextInt();
    
    		zeroOneKP.solve(wt, val, W, n);
    		sc.close();
    	}
    
    }
    

     

    Output for the above problem is

    Enter number of elements 
    3
    Enter weight for 3 elements
    10 20 30
    Enter value for 3 elements
    60 100 120
    Enter knapsack weight 
    50
    
    Items with weight 20 30 are selected by knapsack algorithm.
    Enter number of elements 
    3
    Enter weight for 3 elements
    10 20 30
    Enter value for 3 elements
    60 100 120
    Enter knapsack weight 
    30
    
    Items with weight 10 20 are selected by knapsack algorithm.

     

 0 Comment(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: