Redirecting to
NADOS

Zero One Knapsack

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a number n, representing the count of items.
2. You are given n numbers, representing the values of n items.
3. You are given n numbers, representing the weights of n items.
3. You are given a number "cap", which is the capacity of a bag you've.
4. You are required to calculate and print the maximum value that can be created in the bag without 
     overflowing it's capacity.

Note -> Each item can be taken 0 or 1 number of times. You are not allowed to put the same item 
               again and again.
Input Format 
A number n
v1 v2 .. n number of elements
w1 w2 .. n number of elements
A number cap
Output Format 
A number representing the maximum value that can be created in the bag without overflowing it's capacity
Question Video
Constraints 
1 <= n <= 20
0 <= v1, v2, .. n elements <= 50
0 < w1, w2, .. n elements <= 10
0 < cap <= 10
Sample Input 
5
15 14 10 45 30
2 5 1 3 4
7
Sample Output 
75


  • Editorial

    Brute-force approach:

    From all possible subsets of items, finding a subset whose total weight is at most the capacity of the bag and the total value is maximum.

    Recursive Equation:

    Let wghts[], vals[] be arrays of size n where wghts[i-1] and vals[i-1] are weight and value of the ith item. Let max_val(n, c, wghts[], vals[]) represent the maximum value to fill a bag with capacity "c" with first "n" objects. max_val can be formed either by including or excluding the nth object. nth object will be included if and only if bag capacity is at least the weight of nth object.

    Case-1: nth object is not included

    capacity will remain the same and fill the bag with remaining n-1 items.i.e., max_val(n, c, wghts[], vals[]) = max_val(n-1, c, wghts[], vals[])

    Case: 2 nth object is included:

    capacity will reduce by weight of the nth item and fill the remaining bag with remaining n-1 items i.e., max_val(n, c, wghts[], vals[]) = max_val(n-1, c-wghts[n-1], wghts[], vals[])

    Note: Here wghts[n-1] is the weight of the nth item Final recursively can be written as:

    max_val(n, c, wghts[], vals[]) = maximum_among{ max_val(n-1, c, wghts[], vals[]) max_val(n-1,c-wght[n-1], wghts[], vals[])

    Base conditions:

    1. If capacity of bag = 0(i.e., c = 0) then max_value is 0

    2. If there are no elements(i.e., n = 0) then max_value is 0

    3. Any item will be included in the bag if and only if the capacity of the bag is at least weight of item.

    Recursive algo :

    max_val(n, c, wghts, vals):

             if n is 0 or c is 0 return 0;

             int n_wght = wghts[n-1];//weight of the nth object

             if(n_wght > c):

                //weight of the object is more than capacity

               //hence nth item will not be included

               return max_val(n-1, c, wghts[], vals[])

             else:

                  //nth item can be included

                  int inc = max_val(n-1, c - n_wght, wghts[], vals[])

                  int exc = max_val(n-1, c, wghts[], vals[])

                  return max_among{inc, exc}

    DP with tabulation:

    1. create int dp[n+1][cap+1]

    2. dp[i][j]: max val to fill the bag of capacity 'j' with first 'i' items(0 to i-1)

    3. dp[0][j] = 0 as there are no elements

    4. dp[i][0] = 0 as the capacity of bag = 0

    5. dp[n][cap] is the required soluiton

    6. Filling the table

    for i from 0 to n:

    for j from 0 to cap:

              if i = 0 or j = 0:

                dp[i][j] = 0;

    else:

               int i_wght = wghts[i-1]; //wieght of ith item

               int i_val = vals[i-1]; //value of ith item

               dp[i][j] = dp[i-1][j] // ith item is not included

                if(i_wght > j and i_val + dp[i-1][j-i_wght] > dp[i-1][j]):

                           //ith item can be included

                          dp[i][j] = i_val + dp[i-1][j-i_wght]

    7. Return dp[n][cap]

    Dry run of an exmple:

    Given:

    Capacity = 7

    Table filling:

    Max val to fill bag of capacity 7 with 5 given elements = dp[5][7] = 75.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name