
"""simple docstring"""







def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE )  ->     Dict:







							"""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							,    _SCREAMING_SNAKE_CASE							,    _SCREAMING_SNAKE_CASE							,    _SCREAMING_SNAKE_CASE )
														else:
																					__snake_case     			=       max(
																					    mf_knapsack(i - 1							,    _SCREAMING_SNAKE_CASE							,    _SCREAMING_SNAKE_CASE							,    _SCREAMING_SNAKE_CASE )							,    mf_knapsack(i - 1							,    _SCREAMING_SNAKE_CASE							,    _SCREAMING_SNAKE_CASE							,    j - wt[i - 1] ) + val[i - 1]							,    )
														__snake_case     			=       val
							return f[i][j]
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE )  ->     List[str]:







							"""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   __UpperCamelCase   (					SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE )  ->     Union[str, Any]:







							"""simple docstring"""


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

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

							__snake_case			,   __snake_case     			=       knapsack(_SCREAMING_SNAKE_CASE							,    _SCREAMING_SNAKE_CASE							,    _SCREAMING_SNAKE_CASE							,    _SCREAMING_SNAKE_CASE )
							__snake_case     			=       set()
							_construct_solution(_SCREAMING_SNAKE_CASE							,    _SCREAMING_SNAKE_CASE							,    _SCREAMING_SNAKE_CASE							,    _SCREAMING_SNAKE_CASE							,    _SCREAMING_SNAKE_CASE )

							return optimal_val, example_optional_set
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE )  ->     Union[str, Any]:







							"""simple docstring"""


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


if __name__ == "__main__":
		_SCREAMING_SNAKE_CASE	       =      [3, 2, 4, 4]
		_SCREAMING_SNAKE_CASE	       =      [4, 3, 2, 3]
		_SCREAMING_SNAKE_CASE	       =      4
		_SCREAMING_SNAKE_CASE	       =      6
		_SCREAMING_SNAKE_CASE	       =      [[0] * (w + 1)] + [[0] + [-1] * (w + 1) for _ in range(n + 1)]
		_SCREAMING_SNAKE_CASE	       =      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
		_SCREAMING_SNAKE_CASE	       =      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)


"""simple docstring"""







from heapq import heappop, heappush

import numpy as np
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    )  ->     tuple[float | int, list[tuple[int, int]]]:







							"""simple docstring"""


							__snake_case			,   __snake_case     			=       grid.shape
							__snake_case     			=       [-1, 1, 0, 0]
							__snake_case     			=       [0, 0, -1, 1]
							if allow_diagonal:
														dx += [-1, -1, 1, 1]
														dy += [-1, 1, -1, 1]

							__snake_case			,   __snake_case     			=       [(0, source)], set()
							__snake_case     			=       np.full((rows, cols)							,    np.inf )
							__snake_case     			=       0
							__snake_case     			=       np.empty((rows, cols)							,    dtype=SCREAMING_SNAKE_CASE )
							__snake_case     			=       None

							while queue:
														((__snake_case)			,   (__snake_case))     			=       heappop(SCREAMING_SNAKE_CASE )
														if (x, y) in visited:
																					continue
														visited.add((x, y) )

														if (x, y) == destination:
																					__snake_case     			=       []
																					while (x, y) != source:
																												path.append((x, y) )
																												__snake_case			,   __snake_case     			=       predecessors[x, y]
																					path.append(SCREAMING_SNAKE_CASE )  # add the source manually
																					path.reverse()
																					return matrix[destination], path

														for i in range(len(SCREAMING_SNAKE_CASE ) ):
																					__snake_case			,   __snake_case     			=       x + dx[i], y + dy[i]
																					if 0 <= nx < rows and 0 <= ny < cols:
																												__snake_case     			=       grid[nx][ny]
																												if next_node == 1 and matrix[nx, ny] > dist + 1:
																																			heappush(SCREAMING_SNAKE_CASE							,    (dist + 1, (nx, ny)) )
																																			__snake_case     			=       dist + 1
																																			__snake_case     			=       (x, y)

							return np.inf, []


if __name__ == "__main__":
		import doctest

		doctest.testmod()
