Knapsack 2

Moderate
0/80
profile
Contributed by
3 upvotes
Asked in company
Dell Technologies

Problem statement

There are ‘N’ items numbered from 1, 2, 3, .. N. Each i-th item has a weight, ‘WEIGHT[i]’ and a value, ‘VALUE[i]’.

Ninja has decided to choose some of ‘N’ items and carry them home in a knapsack. The capacity of the knapsack is ‘W’, which means the maximum total weight of items he can carry home is ‘W’.

Find the maximum possible sum of values of items that Ninja takes home.

For Example:

Let ‘WEIGHT’ = [1, 2, 3], ‘VALUE’ = [10, 20, 30] and ‘W’ = 4.
In this case, Ninja can take item 1 and item 3. Then the sum of weights will be 1 + 3 = 4, and the sum of values will be 10 + 30 = 40, which is the maximum possible sum of values Ninja can take home.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T', which denotes the number of test cases.

The next line contains two integers ‘N’ and ‘W’ denoting the number of items and the maximum total weight of items Ninja can take home respectively.

The next line contains ‘N’ space-separated positive integers denoting the elements of array ‘WEIGHT’.

The next line contains ‘N’ space-separated positive integers denoting the elements of array ‘VALUE’.
Output Format : 
For each test case, return the maximum possible sum of values of items that Ninja takes home.
Note : 
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 ≤ T ≤ 10
1 ≤ N ≤ 50
1 ≤ W ≤ 10^7
1 ≤ WEIGHT[i] ≤ W
1 ≤ VALUE[i] ≤ 100
WEIGHT.length = VALUE.length = N

Time limit: 1 sec
Sample Input 1 :
2
3 4
1 2 3
10 20 30
4 5
2 3 5 7
10 30 50 70
Sample Output 1 :
40
50
Explanation of Sample Output 1 :
Test Case 1:
In this case, Ninja can take item 1 and item 3. Then the sum of weights will be 1 + 3 = 4, and the sum of values will be 10 + 30 = 40, which is the maximum possible sum of values Ninja can take home.

Test Case 2:
In this case, Ninja can take either item 1 and item 2, whose sum of weights is 2 + 3 = 5 or item 3 only whose sum of weight is 5. He will choose item 3 only because it will give him the sum of values maximum i.e. 50.
Sample Input 2 :
2
2 4
1 3
10 20
1 2
3
10
Sample Output 2 :
30
0
Explanation of Sample Output 2 :
Test Case 1:
In this case, Ninja can take both items home, because their sum of weights is less than the capacity of the knapsack. Hence he will get sum of values as 10 + 20 = 30.

Test Case 2:
In this case, Ninja can’t take any item home, because the only item available has a weight more than the the capacity of his knapsack. Hence he will get sum of values as 0.
Hint

Generate all possible weights for all possible values of items.

Approaches (3)
Recursive

A simple solution is to generate weights for all possible values of items and take the one which has sum of values as maximum and total weight less than or equal to ‘W’.
 

The maximum total value of items will be simply sum of values of all items. We can loop through all these values and check for a particular value what weight these items have. This weight must be less than or equal to our knapsack capacity ‘W’. And we take a maximum of all these values.
 

Now, for finding the total weight for a particular value we can use recursion because we will generate all possible subsets of items. We are just finding what is the least weight Ninja need to carry to get a particular value.
 

For i-th item there will be two choices:

  1. Get included in the subset - In this case, we include the current item in our final subset and recur for further indices and also the value for which we are finding weight will be reduced by the value of the current item. This case is only possible when the value of the current item is less than the value for which we are finding weight.
  2. Don’t get included - In this case, we don’t include the current item and directly recur for further indices with the same weight.
     

Then we will just take the minimum of these two cases as we want to find the least weight Ninja need to carry.

 

The steps are as follows :

  1. Declare a variable ‘maximumValue’, which will store the maximum value which we can obtain from given values.
  2. for ‘i’ in [0, .. N - 1]:
    • ‘maximumValue’ += value[i]
  3. Declare a variable ‘ans’ to store the maximum value Ninja can take home.
  4. As we need to find a maximum value that has weights of items less than ‘W’, we can iterate from behind.
  5. for ‘v’ in [maximumValue, .. 0]:
    • if knapsackHelper(0, v) <= ‘W’:
      • ‘ans’ = v
      • break
  6. knapsackHelper(idx, val):
    • if ‘idx’ == ‘N’:
      • if ‘val’ == 0:
        • return 0
      • else
        • return infinity
    • Declare two variable ‘inc’ and ‘exc’ which will store weight including the current item and weight excluding current item respectively and initialize them to infinity.
    • if ‘val’ >= ‘VALUE[idx]’:
      • ‘inc’ = knapsackHelper(idx + 1, val - VALUE[idx]) + WEIGHT[idx].
    • ‘exc’ = knapsackHelper(idx + 1, val)
    • return min(inc, exc)
Time Complexity

O( VMAX * ( 2 ^ N ) ), where ‘N’ is the number of items and ‘VMAX’ is the total value of all items.

 

We are generating all subsets of items and doing this for every value from 0 to ‘VMAX’.

Hence the time complexity is O( VMAX * ( 2 ^ N ) ).

Space Complexity

O( N ), where ‘N’ is the number of items.
 

The depth of the recursion tree will be ‘N’. Apart from that, we are not using any space.

Hence the space complexity is O( N ).

Code Solution
(100% EXP penalty)
Knapsack 2
Full screen
Console