0 1 Knapsack Problem – Dynamic Programming Solution

0 1 Knapsack Problem – Dynamic Programming Solution:

Problem Description:

Given weights and values of n items, put these items in a knapsack of capacity M to get the maximum total value in the knapsack.

Note that, you can select items, the sum of whose weight is less than or equal to the capacity of knapsack, W.


Problem Solution:

The problem is to find a subset of items such that – the sum of weight of all the items in the subset should be less than or equal to knapsack capacity out of all subsets that satisfy criteria 1 above, the desired subset is the one in which the sum values of its items is maximum.


Expected Input and Output:

Case-1:

number of items, n=4

weight of items, w[]=2 3 4 5

value of items,  v[]=3 4 5 6

capacity of knapsack, M=5

maximum attainable value of items=7  by collecting first and second item in the knapsack.


Case-2: 

n=3

w[]=3 2 1

v[]=5 3 4

M=5

maximum attainable value of items=9 

by collecting first and last item in the knapsack.


Case-3: 

n=5

w[]=1 2 3 2 2

v[]=8 4 0 4 3

M=4

maximum attainable value of items=13


Solution:

Optimized Solution:


import java.util.*;

public class Knapsack0_1problem {

public int[][] solve(int w, int wt[], int val[], int n) {

System.out.println("Original Values" + w + " " +  n+ " " + Arrays.toString(wt)+ " " + Arrays.toString(val));

int[][] k = new int[n+1][w+1];

System.out.println("K array");

for(int r=0;r<=n;r++)

{

for(int c = 0; c<=w; c++)

{

k[r][c] = 0;

}

}

System.out.println("K array after initializing to 0"+Arrays.toString(k));

System.out.println();

for(int r=0;r<=n;r++)

{

for(int c = 0; c<=w; c++)

{

if(r==0 || c==0)

{

k[r][c] = 0;

}

else

{

if(c<wt[r-1])

{

k[r][c] = k[r-1][c];

}

else

{

k[r][c] = Math.max(k[r-1][c], val[r-1] + k[r-1][c-wt[r-1]]);

}

}

}

}

System.out.println("printing k array after calculation");

for(int p=0; p<=n;p++) 

{

for(int q=0;q<=w;q++) 

{

System.out.print(k[p][q]);

}

System.out.println();

}

return k;

}

public static void main(String[] args) {

Scanner s = new Scanner(System.in);

int w = s.nextInt();

int n = s.nextInt();

int[] wt = new int[n];

int[] val = new int[n];

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

{

wt[i] = s.nextInt();

val[i] = s.nextInt();

}

// System.out.println(w + " " +  n+ " " + Arrays.toString(wt)+ " " + Arrays.toString(val));

Knapsack0_1problem kp = new Knapsack0_1problem();

System.out.println("printing in main method ");

int[][] k = kp.solve(w, wt, val, n);

for(int p=0; p<=n;p++) 

{

for(int q=0;q<=w;q++) 

{

System.out.print(k[p][q]);

}

System.out.println();

}

System.out.println("Maximum profit is: " + k[n][w]);

int i = n, j = w;

while(i>0 && j>0)

{

if(k[i][j] == k[i-1][j])

{

System.out.println(i + " is not included");

i-=1;

}

else

{

System.out.println(i + "is included");

i-=1;

j = j-wt[i];

}

}

}

}


Time Complexity: O(n*w)

Execution:

Successfully Executed


8

4

2

1

3

2

4

5

5

6

printing in main method 

Original Values 8 4 [2, 3, 4, 5] [1, 2, 5, 6]

printing k array after calculation

000000000

001111111

001223333

001255677

001256678

**

000000000

001111111

001223333

001255677

001256678

Maximum profit is: 8

4 is included

3 is not included

2 is included


Recursion:

Approach: A simple solution is to consider all subsets of items and calculate the total weight and value of all subsets. Consider the only subsets whose total weight is smaller than W. From all such subsets, pick the maximum value subset.

Optimal Sub-structure: To consider all subsets of items, there can be two cases for every item.

Case 1: The item is included in the optimal subset.
Case 2: The item is not included in the optimal set.
Therefore, the maximum value that can be obtained from ‘n’ items is the max of the following two values.

Maximum value obtained by n-1 items and W weight (excluding nth item).
Value of nth item plus maximum value obtained by n-1 items and W minus the weight of the nth item (including nth item). If the weight of ‘nth’ item is greater than ‘W’, then the nth item cannot be included and Case 1 is the only possibility.



Below is the implementation of the above approach:

/* A Naive recursive implementation  
of 0-1 Knapsack problem */
class Knapsack { 
  
    // A utility function that returns 
    // maximum of two integers 
    static int max(int a, int b) 
    { 
        return (a > b) ? a : b; 
    } 
  
    // Returns the maximum value that 
    // can be put in a knapsack of 
    // capacity W 
    static int knapSack( 
        int W, int wt[], 
        int val[], int n) 
    { 
        // Base Case 
        if (n == 0 || W == 0) 
            return 0; 
  
        // If weight of the nth item is 
        // more than Knapsack capacity W, 
        // then this item cannot be included 
        // in the optimal solution 
        if (wt[n - 1] > W) 
            return knapSack(W, wt, val, n - 1); 
  
        // Return the maximum of two cases: 
        // (1) nth item included 
        // (2) not included 
        else
            return max( 
                val[n - 1] + knapSack(W - wt[n - 1], 
                                      wt, val, n - 1), 
                knapSack(W, wt, val, n - 1)); 
    } 
  
    // Driver program to test 
    // above function 
    public static void main(String args[]) 
    { 
        int val[] = new int[] { 60, 100, 120 }; 
        int wt[] = new int[] { 10, 20, 30 }; 
        int W = 50; 
        int n = val.length; 
        System.out.println(knapSack(W, wt, val, n)); 
    } 
} 


Output:
220

Explanation:

It should be noted that the above function computes the same sub-problems again and again. See the following recursion tree, K(1, 1) is being evaluated twice. The time complexity of this naive recursive solution is exponential (2^n).

In the following recursion tree, K() refers to knapSack(). The two parameters indicated in the following recursion tree are n and W. The recursion tree is for following sample inputs.
wt[] = {1, 1, 1}, W = 2, val[] = {10, 20, 30}

                       K(n, W)
                       K(3, 2)  
                   /            \ 
                 /                \               
            K(2, 2)                  K(2, 1)
          /       \                  /    \ 
        /           \              /        \
       K(1, 2)      K(1, 1)        K(1, 1)     K(1, 0)
       /  \         /   \          /   \
     /      \     /       \      /       \
K(0, 2)  K(0, 1)  K(0, 1)  K(0, 0)  K(0, 1)   K(0, 0)

Recursion tree for Knapsack capacity 2  units and 3 items of 1 unit weight.

Complexity Analysis:

Time Complexity: O(2^n).
As there are redundant subproblems.
Auxiliary Space :O(1).
As no extra data structure has been used for storing values.

Reference☝ 0-1 Knapsack Problem

                                                         Happy Coding 💻:-)

Comments

Post a Comment

Popular posts from this blog

Valid Username Regular Expression

Valid Username Regular Expression: Problem Description: You are updating the username policy on your company's internal networking platform. According to the policy, a username is considered valid if all the following constraints are satisfied: The username consists of 8 to 30 characters inclusive. If the username consists of less than  or greater than 8 characters, then it is an invalid username. The username can only contain alphanumeric characters and underscores (_). Alphanumeric characters describe the character set consisting of lowercase characters[a-z] , uppercase characters[A-Z] , and digits[0-9]. The first character of the username must be an alphabetic character, i.e., either lowercase character [a-z] or uppercase character [A-Z]. Update the value of regularExpression field in the UsernameValidator class so that the regular expression only matches with valid usernames. Input Format The first line of input contains an integer , describing the total number of usernames. Ea...
Read more

Rotate String in Right Direction in java

Rotate String in Right Direction in java: Program: import java.util.*; public class RotateString { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); char[] ch = new char[n]; for(int i=0;i<n;i++) { ch[i] = s.next().charAt(0); } int r = s.nextInt(); char temp = 'a'; r=r%n; while(r>0) { temp = ch[n-1]; for(int i = n-1; i>0;i--) { ch[i] = ch[i-1]; } ch[0] = temp; System.out.println("r: " + r); for(int i=0;i<n;i++) { System.out.print(ch[i]); } System.out.println(); r--; } for(int i=0;i<n;i++) { System.out.print(ch[i]); } } } Output : 5 a s d f g 3 r: 3 gasdf r: 2 fgasd r: 1 dfgas dfgas                                                            Happy Coding 💻:-)
Read more

Sum of Elements of Lower Triangular Matrix

Sum of Elements of Lower Triangular Matrix: Program: import java.util.Scanner; public class LowerTriangularElementsSum { public static void main(String[] args) { int r, c; Scanner s = new Scanner(System.in); r = s.nextInt(); c = s.nextInt(); if(r!=c) { System.exit(0); } int[][] matrix = new int[r][c]; for(int i = 0; i<r; i++) { for(int j = 0; j<c;j++) { matrix[i][j] = s.nextInt(); } } int sum = 0; for(int i = 0; i<r; i++) { for(int j = 0;j<c; j++) { if(i>=j) { System.out.print(matrix[i][j]); System.out.print(" "); sum+=matrix[i][j]; } } } System.out.println("\nThe sum of Lower triangular elements of a matrix is: " + sum); } } /* In other words, a square matrix is lower triangular if all its entries above the main diagonal are zero.  * Example of a 3 × 3 lower triangular matrix: Diagonal matrices are both upper  *and lower triangular since they have zeroes a...
Read more