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 #Hackerrank #Python #Motivation #AI #React.js #Testing #Interview #SQL #Selenium #LeetCode #Problem Solving #Machine learning #Java #GPT #AWS #API #IT #Algorithms #Github #Jobs #Microservice #Certifications #Projects #Google #Django #Story #Pip #Data Science #Postman #Health #Twitter #Elon Musk #Node.js
5. Solution of Hacker Rank Weather Observation Station 8.Author: neptune | 23rd-Jan-2023
#SQL #Hackerrank
Query the list of CITY names from STATION which have vowels (i.e., a, e, i, o, and u) as both their first and last characters. Your result cannot contain duplicates...
The Blunder | HackerrankAuthor: neptune | 21st-Nov-2022
#SQL #Hackerrank
Write a query calculating the amount of error (i.e.: average monthly salaries), and round it up to the next integer...
7.Solution of Hacker Rank The ReportAuthor: neptune | 23rd-Jan-2023
#SQL #Hackerrank
Problem Statement : generate a report containing three columns: Name, Grade and Mark. Ketty doesn't want the NAMES of those students who received a grade lower than 8...
4. Solution of Hacker Rank Weather Observation Station 6.Author: neptune | 23rd-Jan-2023
#SQL #Hackerrank
Query the list of CITY names starting with vowels (i.e., a, e, i, o, or u) from STATION. Your result cannot contain duplicates...
3. Solution of Hacker Rank Weather Observation Station 4.Author: neptune | 23rd-Jan-2023
#SQL #Hackerrank
Problem Statement : Find the difference between the total number of CITY entries in the table and the number of distinct CITY entries in the table...
The PADS | HackerrankAuthor: neptune | 21st-Nov-2022
#SQL #Hackerrank
Problem Statement: Generate the following two result sets: 1. Query an alphabetically ordered list of all names in OCCUPATIONS, immediately followed by the first letter of each profession...
6. Solution of Hacker Rank Employee Salaries.Author: neptune | 23rd-Jan-2023
#SQL #Hackerrank
Problem Statement : Query that prints a list of employee names for employees in Employee having a salary greater than $2000 per month and experience less than 10 months...
Identifying the Odd One Out in a Series of Strings | HackerrankAuthor: neptune | 15th-Jun-2023
#Hackerrank #Problem Solving
The article presents an algorithm to identify the odd one out in a series of strings efficiently...
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...
2. Solution of Hacker Rank Weather Observation Station 3.Author: neptune | 23rd-Jan-2023
#SQL #Hackerrank
Problem Statement : Query a list of CITY names from STATION for cities that have an even ID number. Print the results in any order, but exclude duplicates from the answer...
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...
Solving the Ice Cream Parlor Problem | HackerrankAuthor: neptune | 04th-Jun-2023
#Hackerrank #Problem Solving
Two friends like to pool their money and go to the ice cream parlour. They always choose two distinct flavours and they spend all of their money...
Backspace String Compare using R | Fresco PlayAuthor: neptune | 05th-Nov-2023
#Hackerrank #Problem Solving
The code implementation in both R and Python solves the "Backspace String Compare" problem using stack data structure...
Git - Recovering Discarded ChangesAuthor: neptune | 13th-Jul-2023
#Github #Problem Solving
We will follow a scenario where a developer is working on a web application and needs to recover a discarded commit to reintroduce a specific feature...
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...
Problem of Merging Two Sorted Linked ListsAuthor: neptune | 02nd-Jun-2023
#Algorithms #Problem Solving
Merging two sorted linked lists efficiently into a single, sorted list can be achieved using optimized algorithms...
Cassandra Products JSON | Fresco PlayAuthor: neptune | 29th-Oct-2023
#Hackerrank #Problem Solving
We'll go through a series of common tasks related to managing data in Cassandra...
Finding the Most Expensive Keyboard and USB Drive within a Budget | HackerrankAuthor: neptune | 05th-Jun-2023
#Hackerrank #Problem Solving
A person wants to determine the most expensive computer keyboard and USB drive that can be purchased with a give budget...
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."..
Join Operations in R | Fresco PlayAuthor: neptune | 29th-Oct-2023
#Hackerrank #Problem Solving
Perform various join operations in R using two data sets, 'flights' and 'weather'...
View More
anonymous | Sept. 19, 2023, 12:52 a.m.
Awesome!