Algos for analysis and design of algorithms
The Algos:-
# GLOBALS
INF=float('inf')
def knapsackDP(profit,weight,total_weight):
''' 0/1 Knapsack using DP '''
n=len(profit)
print("The DP Table is something like:-")
dp=[[0 for i in range(total_weight+1)] for j in range(n+1)]
for i in range(n+1):
for j in range(total_weight+1):
# With 0 elem or 0 weight can't do anything
if(i==0 or j==0):
continue
if(weight[i-1]>j):
# then just take the previous best option for the previous elem at this same weight capacity
dp[i][j]=dp[i-1][j]
else:
# else change the profit for this elem at this weight(j) by comparing with the profit for the previous elem
dp[i][j]=max(dp[i-1][j],profit[i-1]+dp[i-1][j-weight[i-1]])
print(*dp,sep='\n')
print("\n\n")
print(f"Ans is {dp[n][total_weight]}")
def multistageGraph1(graph):
''' The Backward Approach to Multistage Graph '''
print('MULTISTAGE GRAPH BACKWARD APPROACH')
costs=[INF]*len(graph)
# making the cost for the sink to be 0, bcz that's where we wanna reach, so distance with itself will be 0
costs[-1]=0
for i in range(len(graph)-2,-1,-1):
for j in range(len(graph)):
if(graph[i][j]!=INF):
costs[i]=min(costs[i],graph[i][j]+costs[j])
print(costs)
print(f"The minimum cost to reach the sink from source is {costs[0]}")
def multistageGraph2(graph):
''' The Forward Approach to Multistage Graph '''
print("MULTISTAGE GRAPH FORWARD APPROACH")
costs=[INF]*len(graph)
# making the cost for the source to be 0, bcz that's where we wanna start from, so distance with itself will be 0
costs[0]=0
for i in range(1,len(graph)):
for j in range(len(graph)):
if(graph[j][i]!=INF):
costs[i]=min(costs[i],graph[j][i]+costs[j])
print(costs)
print(f"The minimum cost to reach the sink from source is {costs[-1]}")
def jobScheduling(jobs):
''' Greedy Algo for Job Scheduling '''
# Considering the jobs array is of the form [['j1',j1Deadline:int,j1Profit:int],...]
# Sorting the jobs on the basis of their profit
jobs.sort(key=lambda x : x[2],reverse=True)
# help(max)
# Getting the maximum deadline out of all deadlines of the jobs
number_of_slots = max(jobs,key=lambda x:x[1])[1]
available=[True]*number_of_slots
result=[-1]*number_of_slots
print(f"Jobs after sorting them in decreasing order of their profits: {jobs}\n")
print(f'Initial Empty Slots: {result}\n\n')
for job in jobs:
job_name,deadline,profit=job
print(f"Finding a slot for job '{job_name}' with deadline {deadline} and profit {profit}")
for j in range(deadline-1,-1,-1):
# If the slot is available, means if it is free to be used, then just use it and mark it is not avaiable, that is False
if(available[j]==True):
print(f"Slot {j} found for this job, now it is filled. Done with this job!")
available[j]=False
result[j]=job_name
print(f"Now the available slots are {available}")
break
else:
print("No Slot found for this Job.\n\n")
continue
print("\n\n")
print(result)
def main():
# Note: The sample cases are taken from GFG ( Most probably ;) ) for checking the correctness of the algos
# Two sample cases
# jobScheduling([['a',3,24],['b',1,19],['c',2,30],['d',1,20],['e',2,25]])
# jobScheduling([['a',2,100],['c',2,27],['d',1,25],['e',3,19],['b',1,15]])
# Sample for Multistage Graph: Optimal cost is 9
# graph=[ [INF, 1, 2, 5, INF, INF, INF, INF],
# [INF, INF, INF, INF, 4, 11, INF, INF],
# [INF, INF, INF, INF, 9, 5, 16, INF],
# [INF,INF, INF, INF, INF, INF, 2, INF],
# [INF, INF, INF, INF, INF, INF, INF, 18],
# [INF, INF, INF, INF, INF, INF, INF, 13],
# [INF, INF, INF, INF, INF, INF, INF, 2],
# [INF, INF, INF, INF, INF, INF, INF, INF]
# ]
# multistageGraph1(graph)
# multistageGraph2(graph)
# Sample for Knapsack using DP, solution: 220
# profit = [60, 100, 120]
# weight = [10, 20, 30]
# W = 50.
profit=[10,15,40]
weight=[1,2,3]
W=6
knapsackDP(profit,weight,W)
if __name__=="__main__":
main()
The Sorting Algos are mentioned in this previous blogpost(I think last sem):
Quick Sort: This is in CPP I don't remember if I did this in Python couldn't find it so.
Comments
Post a Comment