XYZ Corporation plans to invest in a series of projects over the next year.

Each project requires a certain investment and yields a specific return. Due

to budget constraints, the corporation cannot invest in all projects and

must choose a subset of projects to maximize the total return.

You are provided with the following details:

A list of $)$ projects, each with an associated investment cost and

expected return.

Total budget available for investment.

Your task is to develop a dynamic programming approach to determine the

optimal subset of projects that maximizes the total return without

exceeding the budget.

Input:

Budget: The total amount of money available for investment.

Projects: A list of tuples, each containing two elements:

Investment cost: The amount of money required for the project.

Expected return: The amount of return expected from the project.

Constraints:

You cannot divide a project; each project is either fully funded or

not funded at all.

The total investment in the selected projects must be$,$ at most, the

budget.

Questions:

Formulate the Problem :

Define the state and subproblems for the dynamic programming

approach.

Describe the transition function that you will use to build the

solution.

Explain the base cases and initialization of your dynamic

programming table or array.

Optimal Substructure and Overlapping Subproblems :

Explain why this problem exhibits optimal substructure.

Discuss the property of the overlapping subproblems in the context

of this resource allocation problem.

Given:

Budget: $(B=50)$

Projects: $([(10,60),(20,100),(30,120)])$

Determine the optimal set of projects that yields the maximum return

without exceeding the budget.