

from __future__ import annotations

from statistics import mean





def 					__lowerCamelCase	( UpperCamelCase__   ,							UpperCamelCase__   ,							UpperCamelCase__      ):







							'''simple docstring'''






							snake_case_							=    [0] * no_of_processes
							snake_case_							=    [0] * no_of_processes

							# Initialize remaining_time to waiting_time.

							for i in range(UpperCamelCase__      ):
														snake_case_							=    burst_time[i]
							snake_case_							=    []

							snake_case_							=    0
							snake_case_							=    0

							# When processes are not completed,
							# A process whose arrival time has passed \
							# and has remaining execution time is put into the ready_process.
							# The shortest process in the ready_process, target_process is executed.

							while completed != no_of_processes:
														snake_case_							=    []
														snake_case_							=    -1

														for i in range(UpperCamelCase__      ):
																					if (arrival_time[i] <= total_time) and (remaining_time[i] > 0):
																												ready_process.append(UpperCamelCase__      )

														if len(UpperCamelCase__      ) > 0:
																					snake_case_							=    ready_process[0]
																					for i in ready_process:
																												if remaining_time[i] < remaining_time[target_process]:
																																			snake_case_							=    i
																					total_time += burst_time[target_process]
																					completed += 1
																					snake_case_							=    0
																					snake_case_							=    (
																					    total_time - arrival_time[target_process] - burst_time[target_process]
																					)
														else:
																					total_time += 1

							return waiting_time





def 					__lowerCamelCase	( UpperCamelCase__   ,							UpperCamelCase__   ,							UpperCamelCase__      ):







							'''simple docstring'''






							snake_case_							=    [0] * no_of_processes
							for i in range(UpperCamelCase__      ):
														snake_case_							=    burst_time[i] + waiting_time[i]
							return turn_around_time


if __name__ == "__main__":
					print("""[TEST CASE 01]""")

					_UpperCAmelCase		:   List[Any]										=       4
					_UpperCAmelCase		:   Any										=       [2, 5, 3, 7]
					_UpperCAmelCase		:   Any										=       [0, 0, 0, 0]
					_UpperCAmelCase		:   Tuple										=       calculate_waitingtime(arrival_time, burst_time, no_of_processes)
					_UpperCAmelCase		:   Tuple										=       calculate_turnaroundtime(
					    burst_time, no_of_processes, waiting_time
					)

					# Printing the Result
					print("""PID\tBurst Time\tArrival Time\tWaiting Time\tTurnaround Time""")
					for i, process_id in enumerate(list(range(1, 5))):
										print(
										    F'''{process_id}\t{burst_time[i]}\t\t\t{arrival_time[i]}\t\t\t\t'''
										    F'''{waiting_time[i]}\t\t\t\t{turn_around_time[i]}'''
										)
					print(F'''\nAverage waiting time = {mean(waiting_time):.5f}''')
					print(F'''Average turnaround time = {mean(turn_around_time):.5f}''')







def 					__lowerCamelCase	( UpperCamelCase__   ,							UpperCamelCase__   ,							UpperCamelCase__   ,							UpperCamelCase__      ):







							'''simple docstring'''






							global f  # a global dp table for knapsack
							if f[i][j] < 0:
														if j < wt[i - 1]:
																					snake_case_							=    mf_knapsack(i - 1   ,							UpperCamelCase__   ,							UpperCamelCase__   ,							UpperCamelCase__      )
														else:
																					snake_case_							=    max(
																					    mf_knapsack(i - 1   ,							UpperCamelCase__   ,							UpperCamelCase__   ,							UpperCamelCase__      )   ,							mf_knapsack(i - 1   ,							UpperCamelCase__   ,							UpperCamelCase__   ,							j - wt[i - 1]      ) + val[i - 1]   ,							)
														snake_case_							=    val
							return f[i][j]





def 					__lowerCamelCase	( UpperCamelCase__   ,							UpperCamelCase__   ,							UpperCamelCase__   ,							UpperCamelCase__      ):







							'''simple docstring'''






							snake_case_							=    [[0] * (w + 1) for _ in range(n + 1      )]

							for i in range(1   ,							n + 1      ):
														for w_ in range(1   ,							w + 1      ):
																					if wt[i - 1] <= w_:
																												snake_case_							=    max(val[i - 1] + dp[i - 1][w_ - wt[i - 1]]   ,							dp[i - 1][w_]      )
																					else:
																												snake_case_							=    dp[i - 1][w_]

							return dp[n][w_], dp





def 					__lowerCamelCase	( UpperCamelCase__   ,							UpperCamelCase__   ,							UpperCamelCase__      ):







							'''simple docstring'''






							if not (isinstance(UpperCamelCase__   ,							(list, tuple)      ) and isinstance(UpperCamelCase__   ,							(list, tuple)      )):
														raise ValueError(
														    'Both the weights and values vectors must be either lists or tuples'      )

							snake_case_							=    len(UpperCamelCase__      )
							if num_items != len(UpperCamelCase__      ):
														snake_case_							=    (
														    'The number of weights must be the same as the number of values.\n'
														    F'''But got {num_items} weights and {len(UpperCamelCase__      )} values'''
														)
														raise ValueError(UpperCamelCase__      )
							for i in range(UpperCamelCase__      ):
														if not isinstance(wt[i]   ,							UpperCamelCase__      ):
																					snake_case_							=    (
																					    'All weights must be integers but got weight of '
																					    F'''type {type(wt[i]      )} at index {i}'''
																					)
																					raise TypeError(UpperCamelCase__      )

							snake_case_				,    snake_case_							=    knapsack(UpperCamelCase__   ,							UpperCamelCase__   ,							UpperCamelCase__   ,							UpperCamelCase__      )
							snake_case_							=    set()
							_construct_solution(UpperCamelCase__   ,							UpperCamelCase__   ,							UpperCamelCase__   ,							UpperCamelCase__   ,							UpperCamelCase__      )

							return optimal_val, example_optional_set





def 					__lowerCamelCase	( UpperCamelCase__   ,							UpperCamelCase__   ,							UpperCamelCase__   ,							UpperCamelCase__   ,							UpperCamelCase__      ):







							'''simple docstring'''






							if i > 0 and j > 0:
														if dp[i - 1][j] == dp[i][j]:
																					_construct_solution(UpperCamelCase__   ,							UpperCamelCase__   ,							i - 1   ,							UpperCamelCase__   ,							UpperCamelCase__      )
														else:
																					optimal_set.add(UpperCamelCase__      )
																					_construct_solution(UpperCamelCase__   ,							UpperCamelCase__   ,							i - 1   ,							j - wt[i - 1]   ,							UpperCamelCase__      )


if __name__ == "__main__":
					_UpperCAmelCase		:   Tuple										=       [3, 2, 4, 4]
					_UpperCAmelCase		:   Optional[Any]										=       [4, 3, 2, 3]
					_UpperCAmelCase		:   List[str]										=       4
					_UpperCAmelCase		:   str										=       6
					_UpperCAmelCase		:   Tuple										=       [[0] * (w + 1)] + [[0] + [-1] * (w + 1) for _ in range(n + 1)]
					_UpperCAmelCase				,						_UpperCAmelCase		:   List[Any]										=       knapsack(w, wt, val, n)
					print(optimal_solution)
					print(mf_knapsack(n, wt, val, w))  # switched the n and w

					# testing the dynamic programming problem with example
					# the optimal subset for the above example are items 3 and 4
					_UpperCAmelCase				,						_UpperCAmelCase		:   Any										=       knapsack_with_example_solution(w, wt, val)
					assert optimal_solution == 8
					assert optimal_subset == {3, 4}
					print("""optimal_value = """, optimal_solution)
					print("""An optimal subset corresponding to the optimal value""", optimal_subset)




