



"""simple docstring"""






def 	snake_case_  (				A_ :		List[Any],    A_ :		Dict,    A_ :		Any,    A_ :		int						):


       '''simple docstring'''





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






def 	snake_case_  (				A_ :		Any,    A_ :		Union[str, Any],    A_ :		str,    A_ :		str						):


       '''simple docstring'''





       _lowerCamelCase						:    Dict         =			[[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_:
                            _lowerCamelCase						:    List[Any]         =			max(val[i - 1] + dp[i - 1][w_ - wt[i - 1]],    dp[i - 1][w_]						)
                     else:
                            _lowerCamelCase						:    int         =			dp[i - 1][w_]

       return dp[n][w_], dp






def 	snake_case_  (				A_ :		int,    A_ :		list,    A_ :		list						):


       '''simple docstring'''





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

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

       _lowerCamelCase      ,   _lowerCamelCase						:    Optional[Any]         =			knapsack(A_,    A_,    A_,    A_						)
       _lowerCamelCase						:    set         =			set()
       _construct_solution(A_,    A_,    A_,    A_,    A_						)

       return optimal_val, example_optional_set






def 	snake_case_  (				A_ :		list,    A_ :		list,    A_ :		int,    A_ :		int,    A_ :		set						):


       '''simple docstring'''





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


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






def 	snake_case_  (				A_ :		float						):


       '''simple docstring'''





       if edge <= 0 or not isinstance(A_,    A_						):
              raise ValueError('''Length must be a positive.'''						)
       return 3 * ((25 + 10 * (5 ** (1 / 2))) ** (1 / 2)) * (edge**2)






def 	snake_case_  (				A_ :		float						):


       '''simple docstring'''





       if edge <= 0 or not isinstance(A_,    A_						):
              raise ValueError('''Length must be a positive.'''						)
       return ((15 + (7 * (5 ** (1 / 2)))) / 4) * (edge**3)


if __name__ == "__main__":
   import doctest

   doctest.testmod()


