

'''simple docstring'''







def  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__			)     ->     Union[str, Any]:
       global f  # a global dp table for knapsack
       if f[i][j] < 0:
              if j < wt[i - 1]:
                     A_		   = mf_knapsack(i - 1,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__			)
              else:
                     A_		   = max(
                         mf_knapsack(i - 1,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__			),    mf_knapsack(i - 1,    UpperCAmelCase__,    UpperCAmelCase__,    j - wt[i - 1]			) + val[i - 1],    )
              A_		   = val
       return f[i][j]
def  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__			)     ->     Optional[int]:
       A_		   = [[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_:
                            A_		   = max(val[i - 1] + dp[i - 1][w_ - wt[i - 1]],    dp[i - 1][w_]			)
                     else:
                            A_		   = dp[i - 1][w_]

       return dp[n][w_], dp
def  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__			)     ->     Union[str, Any]:
       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"""			)

       A_		   = len(UpperCAmelCase__			)
       if num_items != len(UpperCAmelCase__			):
              A_		   = (
                  """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__			):
                     A_		   = (
                         """All weights must be integers but got weight of """
                         F'''type {type(wt[i]			)} at index {i}'''
                     )
                     raise TypeError(UpperCAmelCase__			)

       A_   ,     A_		   = knapsack(UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__			)
       A_		   = set()
       _construct_solution(UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__			)

       return optimal_val, example_optional_set
def  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__			)     ->     int:
       # for the current item i at a maximum weight j to be part of an optimal subset,
       # the optimal value at (i, j) must be greater than the optimal value at (i-1, j).
       # where i - 1 means considering only the previous items at the given maximum weight
       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__":
      __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  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__			)     ->     bool:
       A_		   = len(UpperCAmelCase__			)
       A_		   = [[False] * (required_sum + 1) for _ in range(arr_len + 1			)]

       # for each arr value, a sum of zero(0) can be formed by not taking any element
       # hence True/1
       for i in range(arr_len + 1			):
              A_		   = True

       # sum is not zero and set is empty then false
       for i in range(1,    required_sum + 1			):
              A_		   = False

       for i in range(1,    arr_len + 1			):
              for j in range(1,    required_sum + 1			):
                     if arr[i - 1] > j:
                            A_		   = subset[i - 1][j]
                     if arr[i - 1] <= j:
                            A_		   = subset[i - 1][j] or subset[i - 1][j - arr[i - 1]]

       return subset[arr_len][required_sum]


if __name__ == "__main__":
      import doctest

      doctest.testmod()
