In this \"investment\" problem, you are give $T , which is the total amount you
ID: 3700795 • Letter: I
Question
In this "investment" problem, you are give $T, which is the total amount you can invest on n. Product x(x is a number between 0 and n-1) has a cost, c[x] and a profit p[x]. The goal is to maximize the profit without spending more than $T.
Example:
If T = 24, the best investment is to spend $20 (out of $24) to buy products B and C and make $36 in profit.
The API of your program looks like this:
def invest(T, Costs, Profits):
#return a number, which is the best profit you can make.
You will have to do two thing:
* Explain your strategy cleanly and neatly in English
* Write a python program to implement your strategy.
Product A B C D Cost 24 10 10 7 Profit 24 18 18 10Explanation / Answer
Python Code :-
class Investment: #class of Investment
all_products=[]
def __init__(self,product,cost,profit): #initialising all parameteres here like product name,cost,profit
self.product=product
self.cost=cost
self.profit=profit
Investment.all_products.append(self) #attaching all instances of Investment to global variable all_products
#dynamic programming approach
def invest(T, Costs, Profit):
n=len(Costs) #number of products
K = [[0 for x in range(T+1)] for x in range(n+1)] #initialising knapsack with zeros K[i][j] represents maximum profit that can be obtained by with T=j and i number of items
# Build table K[][] in bottom up manner
for i in range(n+1): #iterate through all n
for w in range(T+1): #iterate through all T
if i==0 or w==0:
K[i][w] = 0 #if i==0 or w==0 Our Function Results 0
elif Costs[i-1] <= w:
K[i][w] = max(Profit[i-1] + K[i-1][w-Costs[i-1]], K[i-1][w]) #if Costs[i-1]---> investment remaning at any stage is < the investment we wanted one can either include this in our optimal set or can reject it look at explanation
else:
K[i][w] = K[i-1][w] #here we are no more left with enough investments so assign the previous optimal profix here
return K[n][T] #return the maximum profit One Can Understand This Function By Looking At Explanation
#creating instances of products
Investment('A',24,24)
Investment('B',10,18)
Investment('C',10,18)
Investment('D',7,10)
#Getting costs of all instances of investment and assigning it to Costs
Costs=[i.cost for i in Investment.all_products]
#Getting profit of all instances of investment and assigning it to Profit
Profit=[i.profit for i in Investment.all_products]
#specify investment amount here
T = 24
#assigning length of Costs array to n, this is very important as the implementation is considered
#call the function here
print invest(T , Costs , Profit)
Explanation :-
A simple solution is to consider all subsets of items and calculate the total cost and profit of all subsets. Consider the only subsets whose total cost is smaller than T. From all such subsets, pick the maximum profit subset.
1) Optimal Substructure:
To consider all subsets of items, there can be two cases for every item:
(1) the item is included in the optimal subset,
(2) not included in the optimal set.
Therefore, the maximum profit that can be obtained from n items is max of following two profits.
1) Maximum profit obtained by n-1 items and T cost (excluding nth item).
2) profit of nth item plus maximum profit obtained by n-1 items and T minus cost of the nth item (including nth item).
If cost of nth item is greater than T, then the nth item cannot be included and case 1 is the only possibility.
2) Overlapping Subproblems
Following is recursive implementation that simply follows the recursive structure mentioned below.
SInce we have repeated subproblems here we are using Dynamic Programming.
Example :-
We can see repeated sub problems here.
If you found this answers useful, kindly give thums up(really helpful)
Thanks.