# Zero One Knapsack

#### 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 nv1 v2 .. n number of elementsw1 w2 .. n number of elementsA 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 <= 200 <= v1, v2, .. n elements <= 500 < w1, w2, .. n elements <= 100 < cap <= 10`
Sample Input
`515 14 10 45 302 5 1 3 47`
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.

• Related Topics

Run

Run
Id Name