# 0 1 Knapsack

Posted: 6 Dec, 2020
Difficulty: Easy

## PROBLEM STATEMENT

#### A thief is robbing a store and can carry a maximal weight of W into his knapsack. There are N items and the ith item weighs wi and is of value vi. Considering the constraints of the maximum weight that a knapsack can carry, you have to find and return the maximum value that a thief can generate by stealing items.

##### Input Format:
``````The first line contains a single integer T representing the number of test cases.
The T-test cases are as follows:

Line 1:The first line contains an integer, that denotes the value of N.
Line 2:The following line contains N space-separated integers, that denote the values of the weight of items.
Line 3:The following line contains N space-separated integers, that denote the values associated with the items.
Line 4:The following line contains an integer that denotes the value of W. W denotes the maximum weight that a thief can carry.
``````
##### Output Format :
``````The first and only line of output contains the maximum value that a thief can generate, as described in the task.
The output of every test case is printed in a separate line.
``````
##### Constraints:
``````1 <= T <= 10
1 <= N <= 10^2
1<= wi <= 50
1 <= vi <= 10^2
1 <= W <= 10^3

Time Limit: 1 second
``````
``````Can we solve this using space complexity of not more than O(W)?