99 lines
3.0 KiB
Python
99 lines
3.0 KiB
Python
# Assignment-A3
|
|
|
|
"""
|
|
THIS CODE HAS BEEN TESTED AND IS FULLY OPERATIONAL.
|
|
|
|
Problem Statement: Implement Greedy search algorithm for any of the following application:
|
|
I. Selection Sort
|
|
IV. Job Scheduling Problem
|
|
|
|
Code from ArtificialIntelligence (SPPU - Third Year - Computer Engineering - Content) repository on KSKA Git: https://git.kska.io/sppu-te-comp-content/ArtificialIntelligence
|
|
"""
|
|
|
|
# BEGINNING OF CODE
|
|
# BEGINNING OF SELECTION SORT
|
|
numbers = [] # Empty list to store numbers
|
|
|
|
# Function to take input for numbers
|
|
def input_numbers():
|
|
total = int(input("\nHow many numbers you wish to enter?\nTotal numbers:\t"))
|
|
for i in range(total):
|
|
val = float(input(f"Enter number {i+1}:\t"))
|
|
numbers.append(val)
|
|
print("\nNumbers you've entered are:\t", numbers)
|
|
|
|
# Function for selection sort
|
|
def selection_sort():
|
|
for i in range(len(numbers)):
|
|
min_index = i
|
|
for j in range(i+1, len(numbers)):
|
|
if numbers[j] < numbers[min_index]:
|
|
min_index = j
|
|
numbers[i], numbers[min_index] = numbers[min_index], numbers[i] # Swapping
|
|
print("Numbers sorted in ascending order using selection sort:\t", numbers)
|
|
# END OF SELECTION SORT
|
|
|
|
# BEGINNING OF JOB SCHEDULING
|
|
def job_scheduling():
|
|
jobs = []
|
|
total = int(input("Total jobs to add:\t"))
|
|
|
|
# Take input for jobs
|
|
print("\n", "-"*10, "JOBS", "-"*10, "\n")
|
|
for i in range(total):
|
|
print(f"JOB {i+1} ->")
|
|
job_id = int(input(f"ID for job {i+1}:\t\t"))
|
|
deadline = int(input(f"Deadline for job {i+1}:\t"))
|
|
profit = int(input(f"Profit for job {i+1}:\t"))
|
|
jobs.append((job_id, deadline, profit)) # Index 0 for job_id; Index 1 for deadline; Index 2 for profit
|
|
print(f"\nAdded {total} jobs.")
|
|
print("-"*27, "\n")
|
|
|
|
# Initialize
|
|
jobs.sort(key=lambda x: x[2], reverse=True) # Sort jobs by profit; Using index 2 to access profit
|
|
max_deadline = max(job[1] for job in jobs) # Highest deadline; Using index 1 to access deadline
|
|
slots = [0] * (max_deadline + 1)
|
|
total_profit = 0
|
|
|
|
# Scheduling jobs using greedy strategy
|
|
for job in jobs:
|
|
for i in range(job[1], 0, -1):
|
|
if slots[i] == 0:
|
|
slots[i] = job[0]
|
|
total_profit += job[2]
|
|
break
|
|
|
|
# Print scheduled jobs
|
|
print("Scheduled Jobs:", end=" ")
|
|
for i in range(1, len(slots)):
|
|
if slots[i] != 0:
|
|
print(slots[i], end=" ")
|
|
|
|
print(f"\nTotal Profit: {total_profit}")
|
|
# END OF JOB SCHEDULING
|
|
|
|
|
|
# Main function for menu
|
|
def main():
|
|
while True:
|
|
print("\n\n", "-"*10, "MAIN MENU", "-"*10)
|
|
print("1. Selection Sort")
|
|
print("2. Job Scheduling")
|
|
print("3. Exit")
|
|
choice = int(input("Choose an option (1-3):\t"))
|
|
print("-"*32)
|
|
|
|
if (choice == 1):
|
|
input_numbers()
|
|
selection_sort()
|
|
elif (choice == 2):
|
|
job_scheduling()
|
|
elif (choice == 3):
|
|
print("\n## END OF CODE\n")
|
|
break
|
|
else:
|
|
print("\nPlease choose a valid option (1-3)")
|
|
|
|
main()
|
|
# END OF CODE
|