0/1 Knapsack Problem Statement

A thief is planning to rob a store and can carry a maximum weight 'W' in their knapsack. The store contains 'N' items, each with a known weight and value. Given these constraints, determine the maximum profit that the thief can generate by selecting items to steal, without breaking any item.

Note: Items cannot be broken; they must be taken whole.

Example:

Input:

N = 4, W = 10, weights = [6, 1, 5, 3], values = [3, 6, 1, 4]

Output:

13

Explanation:

The best way to fill the knapsack is by selecting items with weights 6, 1 and 3, making the total value of the knapsack to be 3 + 6 + 4 = 13.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 10^3
• 1 <= W <= 10^3
• 1 <= weights[i] <= 10^3
• 1 <= values[i] <= 10^3

Input:

The first line contains a single integer 'T', representing the number of test cases.
The 'T' test cases are as follows:
The first line contains two integers 'N' and 'W', denoting the number of items and the maximum weight the thief can carry.
The second line contains 'N' space-separated integers representing the weights of the items.
The third line contains 'N' space-separated integers representing the values of the items.

Output:

The output for each test case is a single line containing the maximum profit the thief can generate.