Minimum cost to reduce given number to less than equal to zero

Given array A[] and B[] of size N representing N type of operations. Given a number H, reduce this number to less than equal to 0 by performing the following operation at minimum cost. Choose i^th operation and subtract A[i] from H and the cost incurred will be B[i]. Every operation can be performed any number of times. 

Examples:

Input: A[] = {8, 4, 2}, B[] = {3, 2, 1}, H = 9 
Output: 4
Explanation: The optimal way to solve this problem is to decrease the number H = 9 by the first operation reducing it by A[1] = 8 and the cost incurred is B[1] = 3. H is now 1. Use the third operation to reduce H = 1 by A[3] = 2 cost incurred will be B[3] = 1. Now H is  -1 which is less than equal to 0 hence. in cost = 3 + 1 = 4 number H can be made less than equal to 0.

Input: A[] = {1, 2, 3, 4, 5, 6}, B[] = {1, 3, 9, 27, 81, 243}, H = 100
Output: 100
Explanation: It is optimal to use the first operation 100 times to make H zero in minimum cost.

Naive approach: The basic way to solve the problem is as follows:

The basic way to solve this problem is to generate all possible combinations by using a recursive approach.

Time Complexity: O(H^N)
Auxiliary Space: O(1)

Efficient Approach:  The above approach can be optimized based on the following idea:

Dynamic programming can be used to solve this problem

• dp[i] represents a minimum cost to make I zero from given operations
• recurrence relation: dp[i] = min(dp[i], dp[max(0, i – A[i])] + B[i])

Follow the steps below to solve the problem:

• Declare a dp table of size H + 1 with all values initialized to infinity
• Base case dp[0] = 0
• Iterate from 1 to H to calculate a value for each of them and to do that use all operations from 0 to j and try to make i zero by the minimum cost of these operations.
• Finally, return minimum cost dp[H]

Below is the implementation of the above approach:

Time Complexity: O(N * H)
Auxiliary Space: O(N * H)

Related Articles:

Given array A[] and B[] of size N representing N type of operations. Given a number H, reduce this number to less than equal to 0 by performing the following operation at minimum cost. Choose i^th operation and subtract A[i] from H and the cost incurred will be B[i]. Every operation can be performed any number of times. 

Examples:

Input: A[] = {8, 4, 2}, B[] = {3, 2, 1}, H = 9 
Output: 4
Explanation: The optimal way to solve this problem is to decrease the number H = 9 by the first operation reducing it by A[1] = 8 and the cost incurred is B[1] = 3. H is now 1. Use the third operation to reduce H = 1 by A[3] = 2 cost incurred will be B[3] = 1. Now H is  -1 which is less than equal to 0 hence. in cost = 3 + 1 = 4 number H can be made less than equal to 0.

Input: A[] = {1, 2, 3, 4, 5, 6}, B[] = {1, 3, 9, 27, 81, 243}, H = 100
Output: 100
Explanation: It is optimal to use the first operation 100 times to make H zero in minimum cost.

Naive approach: The basic way to solve the problem is as follows:

The basic way to solve this problem is to generate all possible combinations by using a recursive approach.

Time Complexity: O(H^N)
Auxiliary Space: O(1)

Efficient Approach:  The above approach can be optimized based on the following idea:

Dynamic programming can be used to solve this problem

• dp[i] represents a minimum cost to make I zero from given operations
• recurrence relation: dp[i] = min(dp[i], dp[max(0, i – A[i])] + B[i])

Follow the steps below to solve the problem:

• Declare a dp table of size H + 1 with all values initialized to infinity
• Base case dp[0] = 0
• Iterate from 1 to H to calculate a value for each of them and to do that use all operations from 0 to j and try to make i zero by the minimum cost of these operations.
• Finally, return minimum cost dp[H]

Below is the implementation of the above approach:

Time Complexity: O(N * H)
Auxiliary Space: O(N * H)

Related Articles: