At Nimbus Compute, you need to allocate a limited resource budget across a set of projects. Each project consumes a certain number of resource units and produces a value. Write a function that returns the maximum total value achievable without exceeding the budget.
This is a classic 0/1 resource allocation problem: each project can be selected at most once.
costs: a list of integers where costs[i] is the resource cost of project ivalues: a list of integers where values[i] is the value gained from project icapacity: an integer representing the total available resource unitscapacityExample 1
Input: costs = [2, 3, 4, 5], values = [3, 4, 5, 8], capacity = 5
Output: 8
Selecting only the project with cost 5 gives value 8, which is better than choosing costs 2 + 3 for value 7.
Example 2
Input: costs = [1, 2, 3], values = [6, 10, 12], capacity = 5
Output: 22
Choose projects with costs 2 and 3 for a total value of 10 + 12 = 22.
1 <= len(costs) == len(values) <= 2000 <= capacity <= 10^41 <= costs[i] <= 10^40 <= values[i] <= 10^4costs = [2, 3, 4, 5], values = [3, 4, 5, 8], capacity = 5Output8WhyChoosing the project with cost 5 gives value 8, which is better than combining costs 2 and 3 for value 7.costs = [1, 2, 3], values = [6, 10, 12], capacity = 5Output22WhyThe best choice is the projects with costs 2 and 3, giving total value 22.costs = [4, 5, 6], values = [7, 8, 9], capacity = 3Output0WhyNo project fits within the available capacity, so the maximum value is 0.1 <= len(costs) == len(values) <= 2000 <= capacity <= 10^41 <= costs[i] <= 10^40 <= values[i] <= 10^4def optimal_resource_allocation(costs, values, capacity):