You are given two integer arrays p and q of length n each and an integer maxPower. There are n machines, ith machine consumes p[i] power and produces q[i] quantity. You need to maximize the quantity by consuming not more the maxPower power. Partial consumption of power by a machine is not allowed.
1 <= n <= 36
1 <= maxPower < 10^9
1 <= p[i], q[i] < 10^9
eg:
n = 3
p = [2, 2, 2]
q = [1, 2, 3]
maxPower = 4,
If we select 1st and 2nd index(0 based), the consumed power is 4 and the quantity produced is 5 which is maximum in this case.
I think this is a standard 0/1 knapsack problem but with the given constraints how can we solve this problem.
I guess it can be solved using meet in the middle. (generally for meet in the middle constraints are around n<=40).
First we will divide the array into 2 arrays. Then we can write a recursion for generating all the possible arrays storing information of power consumed and quantity produced. Sort the 2 generated arrays. Then we can use lower/upper bound to find the optimum answer.
anyone help?
do you even consider reading the questions/blogs before replying ?