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.