



"""simple docstring"""




def 						__snake_case						(				SCREAMING_SNAKE_CASE__     :						List[Any]						,  SCREAMING_SNAKE_CASE__     :						Union[str, Any]						,  SCREAMING_SNAKE_CASE__     :						Any						,  SCREAMING_SNAKE_CASE__     :						Tuple    )  ->       Tuple:





     '''simple docstring'''

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

def 						__snake_case						(				SCREAMING_SNAKE_CASE__     :						Dict						,  SCREAMING_SNAKE_CASE__     :						Optional[int]						,  SCREAMING_SNAKE_CASE__     :						Optional[int]						,  SCREAMING_SNAKE_CASE__     :						Tuple    )  ->       Optional[int]:





     '''simple docstring'''

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

     return dp[n][w_], dp

def 						__snake_case						(				SCREAMING_SNAKE_CASE__     :						Optional[int]						,  SCREAMING_SNAKE_CASE__     :						Dict						,  SCREAMING_SNAKE_CASE__     :						Any    )  ->       Optional[Any]:





     '''simple docstring'''

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

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

     _UpperCAmelCase      :     str        =   knapsack(__lowerCAmelCase						,  __lowerCAmelCase						,  __lowerCAmelCase						,  __lowerCAmelCase    )
     _UpperCAmelCase      :     set        =   set()
     _construct_solution(__lowerCAmelCase						,  __lowerCAmelCase						,  __lowerCAmelCase						,  __lowerCAmelCase						,  __lowerCAmelCase    )

     return optimal_val, example_optional_set

def 						__snake_case						(				SCREAMING_SNAKE_CASE__     :						Union[str, Any]						,  SCREAMING_SNAKE_CASE__     :						Any						,  SCREAMING_SNAKE_CASE__     :						Union[str, Any]						,  SCREAMING_SNAKE_CASE__     :						Tuple						,  SCREAMING_SNAKE_CASE__     :						List[str]    )  ->       Dict:





     '''simple docstring'''

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


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





"""simple docstring"""




from collections.abc import Callable






class      UpperCAmelCase_  :



      def __init__(					self					:     Dict					,     A					:     Callable | None = None						):
           # Stores actual heap items.
           _UpperCAmelCase      :     list        =   []
           # Stores indexes of each item for supporting updates and deletion.
           _UpperCAmelCase      :     dict        =   {}
           # Stores current size of heap.
           _UpperCAmelCase      :     Tuple        =   0
           # Stores function used to evaluate the score of an item on which basis ordering
           # will be done.
           _UpperCAmelCase      :     Any        =   key or (lambda A						: x)



      def 						snake_case_ (					self					:     List[Any]					,     A					:     int						):
           return int((i - 1) / 2						) if i > 0 else None



      def 						snake_case_ (					self					:     List[Any]					,     A					:     int						):
           _UpperCAmelCase      :     Tuple        =   int(2 * i + 1						)
           return left if 0 < left < self.size else None



      def 						snake_case_ (					self					:     List[Any]					,     A					:     int						):
           _UpperCAmelCase      :     Tuple        =   int(2 * i + 2						)
           return right if 0 < right < self.size else None



      def 						snake_case_ (					self					:     Optional[int]					,     A					:     int					,     A					:     int						):
           _UpperCAmelCase    ,	_UpperCAmelCase      :     int        =   (
               self.pos_map[self.arr[j][0]],
               self.pos_map[self.arr[i][0]],
           )
           # Then swap the items in the list.
           _UpperCAmelCase    ,	_UpperCAmelCase      :     Any        =   self.arr[j], self.arr[i]



      def 						snake_case_ (					self					:     List[str]					,     A					:     int					,     A					:     int						):
           return self.arr[i][1] < self.arr[j][1]



      def 						snake_case_ (					self					:     Dict					,     A					:     int						):
           _UpperCAmelCase      :     str        =   self._left(A						)
           _UpperCAmelCase      :     str        =   self._right(A						)
           _UpperCAmelCase      :     List[Any]        =   i

           if left is not None and not self._cmp(A					,     A						):
                _UpperCAmelCase      :     Optional[int]        =   left
           if right is not None and not self._cmp(A					,     A						):
                _UpperCAmelCase      :     Any        =   right

           return valid_parent



      def 						snake_case_ (					self					:     Tuple					,     A					:     int						):
           _UpperCAmelCase      :     Tuple        =   self._parent(A						)
           while parent is not None and not self._cmp(A					,     A						):
                self._swap(A					,     A						)
                _UpperCAmelCase    ,	_UpperCAmelCase      :     Dict        =   parent, self._parent(A						)



      def 						snake_case_ (					self					:     Optional[int]					,     A					:     int						):
           _UpperCAmelCase      :     Tuple        =   self._get_valid_parent(A						)
           while valid_parent != index:
                self._swap(A					,     A						)
                _UpperCAmelCase    ,	_UpperCAmelCase      :     Optional[Any]        =   valid_parent, self._get_valid_parent(A						)



      def 						snake_case_ (					self					:     Dict					,     A					:     int					,     A					:     int						):
           if item not in self.pos_map:
                return
           _UpperCAmelCase      :     Any        =   self.pos_map[item]
           _UpperCAmelCase      :     Optional[int]        =   [item, self.key(A						)]
           # Make sure heap is right in both up and down direction.
           # Ideally only one of them will make any change.
           self._heapify_up(A						)
           self._heapify_down(A						)



      def 						snake_case_ (					self					:     List[str]					,     A					:     int						):
           if item not in self.pos_map:
                return
           _UpperCAmelCase      :     str        =   self.pos_map[item]
           del self.pos_map[item]
           _UpperCAmelCase      :     Tuple        =   self.arr[self.size - 1]
           _UpperCAmelCase      :     List[Any]        =   index
           self.size -= 1
           # Make sure heap is right in both up and down direction. Ideally only one
           # of them will make any change- so no performance loss in calling both.
           if self.size > index:
                self._heapify_up(A						)
                self._heapify_down(A						)



      def 						snake_case_ (					self					:     Any					,     A					:     int					,     A					:     int						):
           _UpperCAmelCase      :     Any        =   len(self.arr						)
           if arr_len == self.size:
                self.arr.append([item, self.key(A						)]						)
           else:
                _UpperCAmelCase      :     Any        =   [item, self.key(A						)]
           _UpperCAmelCase      :     List[Any]        =   self.size
           self.size += 1
           self._heapify_up(self.size - 1						)



      def 						snake_case_ (					self					:     Tuple						):
           return self.arr[0] if self.size else None



      def 						snake_case_ (					self					:     Any						):
           _UpperCAmelCase      :     Dict        =   self.get_top()
           if top_item_tuple:
                self.delete_item(top_item_tuple[0]						)
           return top_item_tuple







def 						__snake_case						(				)  ->       None:





     '''simple docstring'''



if __name__ == "__main__":
 import doctest

 doctest.testmod()
