"""

global f # a global dp table for knapsack

if f[i][j] < 0:

if j < wt[i - 1]:

val = mf_knapsack(i - 1, wt, val, j)

else:

val = max(

mf_knapsack(i - 1, wt, val, j),

mf_knapsack(i - 1, wt, val, j - wt[i - 1]) + val[i - 1],

)

f[i][j] = val

dp = [[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_:

dp[i][w_] = max(val[i - 1] + dp[i - 1][w_ - wt[i - 1]], dp[i - 1][w_])

else:

dp[i][w_] = dp[i - 1][w_]

"""

if not (isinstance(wt, (list, tuple)) and isinstance(val, (list, tuple))):

raise ValueError(

"Both the weights and values vectors must be either lists or tuples"

)

num_items = len(wt)

if num_items != len(val):

msg = (

"The number of weights must be the same as the number of values.\n"

f"But got {num_items} weights and {len(val)} values"

)

raise ValueError(msg)

for i in range(num_items):

if not isinstance(wt[i], int):

msg = (

"All weights must be integers but got weight of "

f"type {type(wt[i])} at index {i}"

)

raise TypeError(msg)

optimal_val, dp_table = knapsack(w, wt, val, num_items)

example_optional_set: set = set()

_construct_solution(dp_table, wt, num_items, w, example_optional_set)

"""

# 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(dp, wt, i - 1, j, optimal_set)

else:

optimal_set.add(i)