Problem Brief

Madam C.J. Walker's Business Plan

Madam C.J. Walker, known as the first African-American businesswoman in America, had a business model involving the sale of cosmetics and perfumes for women, which can be likened to a modified 0-1 knapsack problem.

There are n different products available for purchase and resale. The cost of the i item is given by cost[i], and it can be resold for a profit of 2 ** i.

Given the total available to x to invest, determine the maximum profit that can be generated with the given amount of money. Since the answer can be quite large, return the result modulo (10 ** 9 + 7).

Function Description

Complete the function calculateMaximumProfit in the editor.

calculateMaximumProfit has the following parameters:

cost: List[int]: an array of integers representing the cost of each item
x: int: the total amount available to invest

Returns

int: the maximum profit that can be generated modulo (10 ** 9 + 7)

All credit goes to an incredible friend who made it all possible! 🧡

1Example 1

Input

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

Output

Explanation

- Items 0, 1, and 2 for a cost of 44 and obtain a profit of 2 ** 0 + 2 ** 1 + 2 ** 2 = 7 - Items 0 and 4 for a cost of 60 and obtain a profit of 2 ** 0 + 2 ** 4 = 17 - Items 1 and 4 for a cost of 70 and obtain a profit of 2 ** 1 + 2 ** 4 = 18 - Items 2 and 4 for a cost of 64 and obtain a profit of 2 ** 2 + 2 ** 4 = 20 Out of all the possible combinations, the maximum profit is 20 when purchasing items 2 and 4 for a cost of 64.