Modified 0-1 knapsack problem | Frsco Play Hackerrank

The below-given problem is a modification of the standard 0-1 knapsack problem.

An automobile mechanic wants to buy a set of spare parts from a manufacturing unit. The cost of buying the ith spare part is cost[i], and the mechanic charges an amount of 2i for replacing the ith spare part with a new one. The manufacturing unit deals in a total of n items. The mechanic has a total of x amount of money, which the mechanic can spend on buying spare parts.

The goal is to maximise the total amount of money the mechanic can earn for a given amount x. As the answer can be rather large, report the answer as moneyEarned % (109+7), where % denotes modulo operator.

Example:

Suppose there are n = 5 items with costs cost = [10, 20, 14, 40, 50], and the initial amount of money that mechanic has is x = 70.

Some possible combinations of items the mechanic can buy are:

The mechanic can buy items 0, 1, and 2 for a cost of 44 and earn an amount of 20 + 21 + 22= 7.

The mechanic can buy items 0 and 4 for a cost of 60 and earn an amount of 20 + 24= 17.

The mechanic can buy items 1 and 4 for a cost of 70 and earn an amount of 21+ 24= 18.

The mechanic can buy items 2 and 4 for a cost of 64 and earn an amount of 22 + 24 = 20.

Out of all the possible combinations, the maximum money earned is by buying items 2 and 4 for a cost of 64 to obtain a value of 20.

Write a code in Python:

 Complete function findMaximumMoneyEarned (cost, x): 

parameter(s):

cost: an array of integers with cost[i] denoting the cost of buying the ith item.

x: an integer denoting the amount of money the mechanic has.

Function returns :

int: an integer denoting the maximum amount of money the mechanic can earn % (109+7).

Constraints:

1≤ n≤ 105

1≤ cost[i]≤ 105

0≤ x≤ 109

Solution in Python:

    MOD = 10**9 + 7

    def findMaximumMoneyEarned(cost, x):

        n = len(cost)

        # Initialize a 1D list to store the maximum money earned

        dp = [0] * (x + 1)

        for i in range(1, n + 1):

            for j in range(x, cost[i - 1] - 1, -1):

                # Calculate max money either buy or  not buy the spare part (dp[j])

                # print(f"Considering spare part {i}, budget {j}:")

                # If the cost of the spare part >  budget, skip it

                if cost[i - 1] > j:

                    dp[j] = dp[j]

                    # print(f"  Skip part {i} (cost={cost[i-1]})")

                else:

                    dp[j] = max(dp[j], dp[j - cost[i - 1]] + 2 ** (i - 1))

                   #print(f"  Buy part {i} (cost={cost[i-1]})")

        # The answer is stored in dp[x]

        return dp[x] % MOD

    # Example usage

    cost = [10, 20, 14, 40, 50]

    x = 70

    result = findMaximumMoneyEarned(cost, x)

    print(result)  # Output should be 20

    cost = [3, 4, 1]

    x = 8

    result = findMaximumMoneyEarned(cost, x)

    print(result)  # Output should be 7

    cost = [19, 78, 27, 18, 20]

    x = 25

    result = findMaximumMoneyEarned(cost, x)

    print(result)  # Output should be 16

Sample Input 1: 

cost = [3, 4, 1]

x = 8

Sample Output:

7

Explanation:

The mechanic can buy all the items since their total cost is less than or equal to the remaining money.

The total money the mechanic would earn would be 20 + 21 + 22 = 7. The output would be 7 % 109+7 , i.e. 7.

Sample Case 1:

cost= [19, 78, 27, 18, 20]

x = 25

Sample Output:

16

Explanation:

The optimal solution would be to buy the last item, generating an amount of 24 = 16. The output will be 16 % (109+7), i.e. 16.