Modified 0-1 knapsack problem | Frsco Play Hackerrank
Author: neptune | 05th-Nov-2023
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.
#JavaScript #Python #Hackerrank #Motivation #AI #React.js #Interview #Testing #SQL #Selenium #LeetCode #Problem Solving #Machine learning #IT #API #Java #GPT #AWS #Algorithms #Github #Projects #Jobs #Django #Microservice #Certifications #Node.js #TCS #Google #Story #Pip #Data Science #Postman #Health #Twitter #Elon Musk
1. Basic SQL Select Query of Hacker Rank.Author: neptune | 20th-Apr-2022
#SQL #Hackerrank
Problem Statement : Query all columns for all American cities in the CITY table with populations larger than 100000. The CountryCode for America is USA...
AngularJS - Know Tech Frameworks | Fresco PlayAuthor: neptune | 05th-Nov-2023
#Hackerrank #Problem Solving
Build an application that displays the framework details using AngularJS routing. We will build an application that displays the Tech Frontend and Backend frameworks...
PySpark Milestone Black Friday Sales Data | Fresco Play HackerrankAuthor: neptune | 05th-Nov-2023
#Data Science #Hackerrank
Welcome to the Spark Challenge. You are provided with the Black Friday sales data and we as a big data developer needs to analyze and fetch the required data...
Python - Number Based Problem | HackerrankAuthor: neptune | 17th-Aug-2023
#Hackerrank #Problem Solving
Determine whether the number in descending order is a prime or not. If the number is a prime, then print "Sorted Number is a prime number," otherwise, print "Sorted Number is not a prime number."..
View More
anonymous | Sept. 19, 2023, 12:52 a.m.
Awesome!