0-1 Knapsack

Given two integer arrays A and B of size N each which represent values and weights associated with N items respectively.

Also given an integer C which represents knapsack capacity.

Find out the maximum value subset of A such that sum of the weights of this subset is smaller than or equal to C.

NOTE:

• You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).

1 <= N <= 10³

1 <= C <= 10³

1 <= A[i], B[i] <= 10³

First argument is an integer array A of size N denoting the values on N items.

Second argument is an integer array B of size N denoting the weights on N items.

Third argument is an integer C denoting the knapsack capacity.

Return a single integer denoting the maximum value subset of A such that sum of the weights of this subset is smaller than or equal to C.

Input 1:

 A = [60, 100, 120]
 B = [10, 20, 30]
 C = 50

Input 2:

 A = [10, 20, 30, 40]
 B = [12, 13, 15, 19]
 C = 10

Output 1:

 220

Output 2:

 0

Explanation 1:

 Taking items with weight 20 and 30 will give us the maximum value i.e 100 + 120 = 220

Explanation 2:

 Knapsack capacity is 10 but each item has weight greater than 10 so no items can be considered in the knapsack therefore answer is 0.