Modified 0-1 knapsack problem | Frsco Play Hackerrank

Author: neptune | 05th-Nov-2023
šŸ·ļø #Hackerrank #Problem Solving

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.





šŸ‘‰ Read More
The Blunder | Hackerrank
5. Solution of Hacker Rank Weather Observation Station 8.
7.Solution of Hacker Rank The Report
Identifying the Odd One Out in a Series of Strings | Hackerrank
4. Solution of Hacker Rank Weather Observation Station 6.
3. Solution of Hacker Rank Weather Observation Station 4.
The PADS | Hackerrank
6. Solution of Hacker Rank Employee Salaries.
1. Basic SQL Select Query of Hacker Rank.
Generate Fibonacci Sequence - JavaScript | Hackerank
Team Formation Hackerrank | Julia
2. Solution of Hacker Rank Weather Observation Station 3.
Weather Observation Station 18 | Hackerrank
Solving the Ice Cream Parlor Problem | Hackerrank
AngularJS - Know Tech Frameworks | Fresco Play
PySpark Milestone Black Friday Sales Data | Fresco Play Hackerrank
Backspace String Compare using R | Fresco Play
Top Earners | HackerRank
Git - Recovering Discarded Changes
Python - Number Based Problem | Hackerrank
Explore more Blogs...