

import inspect
import unittest
from typing import List

import numpy as np

from transformers import EfficientFormerConfig
from transformers.testing_utils import require_tf, require_vision, slow
from transformers.utils import cached_property, is_tf_available, is_vision_available

from ...test_configuration_common import ConfigTester
from ...test_modeling_tf_common import TFModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_tf_available():
			import tensorflow as tf

			from transformers import (
			    TFEfficientFormerForImageClassification,
			    TFEfficientFormerForImageClassificationWithTeacher,
			    TFEfficientFormerModel,
			)
			from transformers.models.efficientformer.modeling_tf_efficientformer import (
			    TF_EFFICIENTFORMER_PRETRAINED_MODEL_ARCHIVE_LIST,
			)


if is_vision_available():
			from PIL import Image

			from transformers import EfficientFormerImageProcessor






class _UpperCamelCase							:
		'''simple docstring'''







		def __init__(			self							: int      ,      a							: Optional[Any]      ,      a							: int = 13      ,      a							: int = 64      ,      a							: int = 2      ,      a							: int = 3      ,      a							: int = 3      ,      a							: bool = True      ,      a							: bool = True      ,      a							: int = 128      ,      a							: Any=[16, 32, 64, 128]      ,      a							: int = 7      ,      a							: int = 4      ,      a							: int = 37      ,      a							: str = "gelu"      ,      a							: float = 0.1      ,      a							: float = 0.1      ,      a							: int = 10      ,      a							: float = 0.02      ,      a							: int = 2      ,      a							: int = 1      ,      a							: int = 128      ,      a							: List[int] = [2, 2, 2, 2]      ,      a							: int = 2      ,      a							: int = 2      ,      )							->       Any:

			"""simple docstring"""

			SCREAMING_SNAKE_CASE   :      Union[str, Any]				     =       parent
			SCREAMING_SNAKE_CASE   :      Optional[int]				     =       batch_size
			SCREAMING_SNAKE_CASE   :      str				     =       image_size
			SCREAMING_SNAKE_CASE   :      Union[str, Any]				     =       patch_size
			SCREAMING_SNAKE_CASE   :      Optional[Any]				     =       num_channels
			SCREAMING_SNAKE_CASE   :      int				     =       is_training
			SCREAMING_SNAKE_CASE   :      str				     =       use_labels
			SCREAMING_SNAKE_CASE   :      Tuple				     =       hidden_size
			SCREAMING_SNAKE_CASE   :      Union[str, Any]				     =       num_hidden_layers
			SCREAMING_SNAKE_CASE   :      Optional[int]				     =       num_attention_heads
			SCREAMING_SNAKE_CASE   :      Tuple				     =       intermediate_size
			SCREAMING_SNAKE_CASE   :      List[str]				     =       hidden_act
			SCREAMING_SNAKE_CASE   :      List[Any]				     =       hidden_dropout_prob
			SCREAMING_SNAKE_CASE   :      int				     =       attention_probs_dropout_prob
			SCREAMING_SNAKE_CASE   :      int				     =       type_sequence_label_size
			SCREAMING_SNAKE_CASE   :      Optional[int]				     =       initializer_range
			SCREAMING_SNAKE_CASE   :      str				     =       encoder_stride
			SCREAMING_SNAKE_CASE   :      Dict				     =       num_attention_outputs
			SCREAMING_SNAKE_CASE   :      Any				     =       embed_dim
			SCREAMING_SNAKE_CASE   :      List[Any]				     =       embed_dim + 1
			SCREAMING_SNAKE_CASE   :      Dict				     =       resolution
			SCREAMING_SNAKE_CASE   :      str				     =       depths
			SCREAMING_SNAKE_CASE   :      Optional[int]				     =       hidden_sizes
			SCREAMING_SNAKE_CASE   :      str				     =       dim
			SCREAMING_SNAKE_CASE   :      List[str]				     =       mlp_expansion_ratio
		def 							__UpperCamelCase (			self							: Optional[Any]	)							->       str:

			"""simple docstring"""

			SCREAMING_SNAKE_CASE   :      str				     =       floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]	)

			SCREAMING_SNAKE_CASE   :      int				     =       None
			if self.use_labels:
				SCREAMING_SNAKE_CASE   :      Optional[int]				     =       ids_tensor([self.batch_size]      ,      self.type_sequence_label_size	)

			SCREAMING_SNAKE_CASE   :      Any				     =       self.get_config()

			return config, pixel_values, labels
		def 							__UpperCamelCase (			self							: Union[str, Any]	)							->       Any:

			"""simple docstring"""

			return EfficientFormerConfig(
			    image_size=self.image_size      ,      patch_size=self.patch_size      ,      num_channels=self.num_channels      ,      hidden_size=self.hidden_size      ,      num_hidden_layers=self.num_hidden_layers      ,      num_attention_heads=self.num_attention_heads      ,      intermediate_size=self.intermediate_size      ,      hidden_act=self.hidden_act      ,      hidden_dropout_prob=self.hidden_dropout_prob      ,      attention_probs_dropout_prob=self.attention_probs_dropout_prob      ,      is_decoder=a      ,      initializer_range=self.initializer_range      ,      encoder_stride=self.encoder_stride      ,      resolution=self.resolution      ,      depths=self.depths      ,      hidden_sizes=self.hidden_sizes      ,      dim=self.dim      ,      mlp_expansion_ratio=self.mlp_expansion_ratio      ,      )
		def 							__UpperCamelCase (			self							: Any      ,      a							: Union[str, Any]      ,      a							: Tuple      ,      a							: Union[str, Any]	)							->       List[str]:

			"""simple docstring"""

			SCREAMING_SNAKE_CASE   :      Tuple				     =       TFEfficientFormerModel(config=a	)
			SCREAMING_SNAKE_CASE   :      int				     =       model(a      ,      training=a	)
			self.parent.assertEqual(result.last_hidden_state.shape      ,      (self.batch_size, self.seq_length, self.hidden_size)	)
		def 							__UpperCamelCase (			self							: Optional[Any]      ,      a							: str      ,      a							: Union[str, Any]      ,      a							: Dict	)							->       Dict:

			"""simple docstring"""

			SCREAMING_SNAKE_CASE   :      List[str]				     =       self.type_sequence_label_size
			SCREAMING_SNAKE_CASE   :      Tuple				     =       TFEfficientFormerForImageClassification(a	)
			SCREAMING_SNAKE_CASE   :      List[Any]				     =       model(a      ,      labels=a      ,      training=a	)
			self.parent.assertEqual(result.logits.shape      ,      (self.batch_size, self.type_sequence_label_size)	)

			# test greyscale images
			SCREAMING_SNAKE_CASE   :      Dict				     =       1
			SCREAMING_SNAKE_CASE   :      Union[str, Any]				     =       TFEfficientFormerForImageClassification(a	)

			SCREAMING_SNAKE_CASE   :      str				     =       floats_tensor([self.batch_size, 1, self.image_size, self.image_size]	)
			SCREAMING_SNAKE_CASE   :      List[str]				     =       model(a      ,      labels=a	)
			self.parent.assertEqual(result.logits.shape      ,      (self.batch_size, self.type_sequence_label_size)	)






		def 							__UpperCamelCase (			self							: List[str]	)							->       Optional[int]:

			"""simple docstring"""

			SCREAMING_SNAKE_CASE   :      List[Any]				     =       self.prepare_config_and_inputs()
			SCREAMING_SNAKE_CASE   :      Optional[Any]				     =       config_and_inputs
			SCREAMING_SNAKE_CASE   :      Tuple				     =       {"pixel_values": pixel_values}
			return config, inputs_dict






@require_tf
class _UpperCamelCase							(							__A							,	__A							,	unittest.TestCase   ):
		'''simple docstring'''







		lowerCamelCase__           =(
		    (
		        TFEfficientFormerModel,
		        TFEfficientFormerForImageClassificationWithTeacher,
		        TFEfficientFormerForImageClassification,
		    )
		    if is_tf_available()
		    else ()
		)
		lowerCamelCase__           =(
		    {
		        'feature-extraction': TFEfficientFormerModel,
		        'image-classification': (
		            TFEfficientFormerForImageClassification,
		            TFEfficientFormerForImageClassificationWithTeacher,
		        ),
		    }
		    if is_tf_available()
		    else {}
		)

		lowerCamelCase__           =False

		lowerCamelCase__           =False
		lowerCamelCase__           =False
		lowerCamelCase__           =False
		lowerCamelCase__           =False
		def 							__UpperCamelCase (			self							: List[Any]	)							->       Union[str, Any]:

			"""simple docstring"""

			SCREAMING_SNAKE_CASE   :      Dict				     =       TFEfficientFormerModelTester(self	)
			SCREAMING_SNAKE_CASE   :      Optional[int]				     =       ConfigTester(
			    self      ,      config_class=a      ,      has_text_modality=a      ,      hidden_size=37	)
		def 							__UpperCamelCase (			self							: Optional[int]	)							->       Optional[Any]:

			"""simple docstring"""

			self.config_tester.run_common_tests()
		@unittest.skip(reason="EfficientFormer does not use inputs_embeds"	)
		def 							__UpperCamelCase (			self							: List[str]	)							->       str:

			"""simple docstring"""

			pass
		@unittest.skip(reason="EfficientFormer does not support input and output embeddings"	)
		def 							__UpperCamelCase (			self							: Any	)							->       Dict:

			"""simple docstring"""

			pass
		def 							__UpperCamelCase (			self							: Tuple	)							->       Union[str, Any]:

			"""simple docstring"""

			SCREAMING_SNAKE_CASE   :      Optional[int]				     =       self.model_tester.prepare_config_and_inputs_for_common()

			for model_class in self.all_model_classes:
				SCREAMING_SNAKE_CASE   :      Optional[Any]				     =       model_class(a	)
				SCREAMING_SNAKE_CASE   :      Any				     =       inspect.signature(model.call	)
				# signature.parameters is an OrderedDict => so arg_names order is deterministic
				SCREAMING_SNAKE_CASE   :      Dict				     =       [*signature.parameters.keys()]

				SCREAMING_SNAKE_CASE   :      Tuple				     =       ["pixel_values"]
				self.assertListEqual(arg_names[:1]      ,      a	)
		def 							__UpperCamelCase (			self							: Optional[int]	)							->       Optional[Any]:

			"""simple docstring"""

			def check_hidden_states_output(a							: Optional[int]      ,      a							: Any      ,      a							: List[Any]	):
				SCREAMING_SNAKE_CASE   :      Dict				     =       model_class(a	)

				SCREAMING_SNAKE_CASE   :      str				     =       model(**self._prepare_for_class(a      ,      a	)      ,      training=a	)
				SCREAMING_SNAKE_CASE   :      Any				     =       outputs.encoder_hidden_states if config.is_encoder_decoder else outputs.hidden_states

				SCREAMING_SNAKE_CASE   :      Optional[int]				     =       getattr(
				    self.model_tester      ,      "expected_num_hidden_layers"      ,      self.model_tester.num_hidden_layers + 1	)
				self.assertEqual(len(a	)      ,      a	)

				if hasattr(self.model_tester      ,      "encoder_seq_length"	):
					SCREAMING_SNAKE_CASE   :      Any				     =       self.model_tester.encoder_seq_length
					if hasattr(self.model_tester      ,      "chunk_length"	) and self.model_tester.chunk_length > 1:
						SCREAMING_SNAKE_CASE   :      Union[str, Any]				     =       seq_length * self.model_tester.chunk_length
				else:
					SCREAMING_SNAKE_CASE   :      Union[str, Any]				     =       self.model_tester.seq_length

				self.assertListEqual(
				    list(hidden_states[-1].shape[-2:]	)      ,      [seq_length, self.model_tester.hidden_size]      ,      )

				if config.is_encoder_decoder:
					SCREAMING_SNAKE_CASE   :      Optional[Any]				     =       outputs.decoder_hidden_states

					self.asseretIsInstance(a      ,      (list, tuple)	)
					self.assertEqual(len(a	)      ,      a	)
					SCREAMING_SNAKE_CASE   :      Tuple				     =       getattr(self.model_tester      ,      "seq_length"      ,      a	)
					SCREAMING_SNAKE_CASE   :      Optional[Any]				     =       getattr(self.model_tester      ,      "decoder_seq_length"      ,      a	)

					self.assertListEqual(
					    list(hidden_states[-1].shape[-2:]	)      ,      [decoder_seq_length, self.model_tester.hidden_size]      ,      )

			SCREAMING_SNAKE_CASE   :      Any				     =       self.model_tester.prepare_config_and_inputs_for_common()

			for model_class in self.all_model_classes:
				SCREAMING_SNAKE_CASE   :      int				     =       True
				check_hidden_states_output(a      ,      a      ,      a	)

				# check that output_hidden_states also work using config
				del inputs_dict["output_hidden_states"]
				SCREAMING_SNAKE_CASE   :      str				     =       True

				check_hidden_states_output(a      ,      a      ,      a	)
		def 							__UpperCamelCase (			self							: Dict      ,      a							: Optional[int]      ,      a							: List[str]      ,      a							: Optional[Any]=False	)							->       Optional[Any]:

			"""simple docstring"""

			SCREAMING_SNAKE_CASE   :      Dict				     =       super()._prepare_for_class(a      ,      a      ,      return_labels=a	)

			if return_labels:
				if model_class.__name__ == "TFEfficientFormerForImageClassificationWithTeacher":
					del inputs_dict["labels"]

			return inputs_dict
		def 							__UpperCamelCase (			self							: Tuple	)							->       List[str]:

			"""simple docstring"""

			SCREAMING_SNAKE_CASE   :      Tuple				     =       self.model_tester.prepare_config_and_inputs()
			self.model_tester.create_and_check_model(*a	)
		@unittest.skip(reason="EfficientFormer does not implement masked image modeling yet"	)
		def 							__UpperCamelCase (			self							: Any	)							->       Any:

			"""simple docstring"""

			SCREAMING_SNAKE_CASE   :      Dict				     =       self.model_tester.prepare_config_and_inputs()
			self.model_tester.create_and_check_for_masked_image_modeling(*a	)
		def 							__UpperCamelCase (			self							: Dict	)							->       Optional[Any]:

			"""simple docstring"""

			SCREAMING_SNAKE_CASE   :      Optional[Any]				     =       self.model_tester.prepare_config_and_inputs()
			self.model_tester.create_and_check_for_image_classification(*a	)
		@slow
		def 							__UpperCamelCase (			self							: int	)							->       Any:

			"""simple docstring"""

			for model_name in TF_EFFICIENTFORMER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
				SCREAMING_SNAKE_CASE   :      List[Any]				     =       TFEfficientFormerModel.from_pretrained(a	)
				self.assertIsNotNone(a	)
		def 							__UpperCamelCase (			self							: Optional[int]	)							->       List[str]:

			"""simple docstring"""

			SCREAMING_SNAKE_CASE   :      Tuple				     =       self.model_tester.prepare_config_and_inputs_for_common()
			SCREAMING_SNAKE_CASE   :      Optional[Any]				     =       True

			SCREAMING_SNAKE_CASE   :      str				     =       getattr(self.model_tester      ,      "seq_length"      ,      a	)
			SCREAMING_SNAKE_CASE   :      Optional[int]				     =       getattr(self.model_tester      ,      "encoder_seq_length"      ,      a	)
			SCREAMING_SNAKE_CASE   :      List[str]				     =       getattr(self.model_tester      ,      "key_length"      ,      a	)
			SCREAMING_SNAKE_CASE   :      int				     =       getattr(self.model_tester      ,      "chunk_length"      ,      a	)

			if chunk_length is not None and hasattr(self.model_tester      ,      "num_hashes"	):
				SCREAMING_SNAKE_CASE   :      List[Any]				     =       encoder_seq_length * self.model_tester.num_hashes

			for model_class in self.all_model_classes:
				SCREAMING_SNAKE_CASE   :      Any				     =       True
				SCREAMING_SNAKE_CASE   :      Optional[int]				     =       False
				SCREAMING_SNAKE_CASE   :      Tuple				     =       True
				SCREAMING_SNAKE_CASE   :      Any				     =       model_class(a	)

				SCREAMING_SNAKE_CASE   :      Tuple				     =       model(**self._prepare_for_class(a      ,      a	)      ,      training=a	)
				SCREAMING_SNAKE_CASE   :      Dict				     =       outputs.encoder_attentions if config.is_encoder_decoder else outputs.attentions
				self.assertEqual(len(a	)      ,      self.model_tester.num_attention_outputs	)

				# check that output_attentions also work using config
				del inputs_dict["output_attentions"]
				SCREAMING_SNAKE_CASE   :      Union[str, Any]				     =       True
				SCREAMING_SNAKE_CASE   :      Dict				     =       model_class(a	)
				SCREAMING_SNAKE_CASE   :      Any				     =       model(**self._prepare_for_class(a      ,      a	)      ,      training=a	)

				SCREAMING_SNAKE_CASE   :      List[Any]				     =       outputs.encoder_attentions if config.is_encoder_decoder else outputs.attentions
				self.assertEqual(len(a	)      ,      self.model_tester.num_attention_outputs	)

				if chunk_length is not None:
					self.assertListEqual(
					    list(attentions[0].shape[-4:]	)      ,      [self.model_tester.num_attention_heads, encoder_seq_length, chunk_length, encoder_key_length]      ,      )
				else:
					self.assertListEqual(
					    list(attentions[0].shape[-3:]	)      ,      [self.model_tester.num_attention_heads, encoder_seq_length, encoder_key_length]      ,      )






		def 							__UpperCamelCase (			self							: Optional[int]	)							->       List[str]:

			"""simple docstring"""

			SCREAMING_SNAKE_CASE   :      Tuple				     =       self.model_tester.prepare_config_and_inputs_for_common()

			for model_class in self.all_model_classes:
				# Prepare our model
				SCREAMING_SNAKE_CASE   :      str				     =       model_class(a	)
				# These are maximally general inputs for the model, with multiple None dimensions
				# Hopefully this will catch any conditionals that fail for flexible shapes
				SCREAMING_SNAKE_CASE   :      Any				     =       {
				    key: tf.keras.Input(shape=val.shape[1:]      ,      dtype=val.dtype      ,      name=a	)
				    for key, val in model.input_signature.items()
				    if key in model.dummy_inputs
				}
				SCREAMING_SNAKE_CASE   :      Optional[int]				     =       model(a	)
				self.assertTrue(outputs_dict is not None	)

def  lowerCamelCase__ (					):
	SCREAMING_SNAKE_CASE   :      Tuple				     =       Image.open("./tests/fixtures/tests_samples/COCO/000000039769.png")
	return image






@require_tf
@require_vision
class _UpperCamelCase							(							unittest.TestCase   ):
		'''simple docstring'''







		@cached_property
		def 							__UpperCamelCase (			self							: Dict	)							->       Dict:

			"""simple docstring"""

			return (
			    EfficientFormerImageProcessor.from_pretrained("snap-research/efficientformer-l1-300"	)
			    if is_vision_available()
			    else None
			)
		@slow
		def 							__UpperCamelCase (			self							: Tuple	)							->       List[str]:

			"""simple docstring"""

			SCREAMING_SNAKE_CASE   :      List[str]				     =       TFEfficientFormerForImageClassification.from_pretrained("snap-research/efficientformer-l1-300"	)
			SCREAMING_SNAKE_CASE   :      Optional[Any]				     =       self.default_image_processor
			SCREAMING_SNAKE_CASE   :      Any				     =       prepare_img()
			SCREAMING_SNAKE_CASE   :      Tuple				     =       image_processor(images=a      ,      return_tensors="tf"	)
			# forward pass
			SCREAMING_SNAKE_CASE   :      Tuple				     =       model(**a      ,      training=a	)
			# verify the logits
			SCREAMING_SNAKE_CASE   :      List[Any]				     =       tf.TensorShape((1, 1000)	)
			self.assertEqual(outputs.logits.shape      ,      a	)
			SCREAMING_SNAKE_CASE   :      str				     =       tf.constant([-0.0555, 0.4825, -0.0852]	)
			self.assertTrue(np.allclose(outputs.logits[0, :3]      ,      a      ,      atol=1e-4	)	)






		@slow
		def 							__UpperCamelCase (			self							: Union[str, Any]	)							->       str:

			"""simple docstring"""

			SCREAMING_SNAKE_CASE   :      Any				     =       TFEfficientFormerForImageClassificationWithTeacher.from_pretrained(
			    "snap-research/efficientformer-l1-300"	)
			SCREAMING_SNAKE_CASE   :      Union[str, Any]				     =       self.default_image_processor
			SCREAMING_SNAKE_CASE   :      Dict				     =       prepare_img()
			SCREAMING_SNAKE_CASE   :      str				     =       image_processor(images=a      ,      return_tensors="tf"	)
			# forward pass
			SCREAMING_SNAKE_CASE   :      Optional[int]				     =       model(**a      ,      training=a	)
			# verify the logits
			SCREAMING_SNAKE_CASE   :      List[Any]				     =       tf.TensorShape((1, 1000)	)
			self.assertEqual(outputs.logits.shape      ,      a	)
			SCREAMING_SNAKE_CASE   :      Tuple				     =       tf.constant([-0.1312, 0.4353, -1.0499]	)
			self.assertTrue(np.allclose(outputs.logits[0, :3]      ,      a      ,      atol=1e-4	)	)


def  lowerCamelCase__ (					_a							,			_a							,			_a							,			_a):
	global f  # a global dp table for knapsack
	if f[i][j] < 0:
		if j < wt[i - 1]:
			SCREAMING_SNAKE_CASE   :      Union[str, Any]				     =       mf_knapsack(i - 1							,			_a							,			_a							,			_a)
		else:
			SCREAMING_SNAKE_CASE   :      Any				     =       max(
			    mf_knapsack(i - 1							,			_a							,			_a							,			_a)							,			mf_knapsack(i - 1							,			_a							,			_a							,			j - wt[i - 1]) + val[i - 1]							,			)
		SCREAMING_SNAKE_CASE   :      Tuple				     =       val
	return f[i][j]

def  lowerCamelCase__ (					_a							,			_a							,			_a							,			_a):
	SCREAMING_SNAKE_CASE   :      Union[str, 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_:
				SCREAMING_SNAKE_CASE   :      Union[str, Any]				     =       max(val[i - 1] + dp[i - 1][w_ - wt[i - 1]]							,			dp[i - 1][w_])
			else:
				SCREAMING_SNAKE_CASE   :      int				     =       dp[i - 1][w_]

	return dp[n][w_], dp

def  lowerCamelCase__ (					_a							,			_a							,			_a):
	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")

	SCREAMING_SNAKE_CASE   :      int				     =       len(_a)
	if num_items != len(_a):
		SCREAMING_SNAKE_CASE   :      List[str]				     =       (
		    "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):
			SCREAMING_SNAKE_CASE   :      int				     =       (
			    "All weights must be integers but got weight of "
			    f"type {type(wt[i])} at index {i}"
			)
			raise TypeError(_a)

	SCREAMING_SNAKE_CASE     ,SCREAMING_SNAKE_CASE   :      Tuple				     =       knapsack(_a							,			_a							,			_a							,			_a)
	SCREAMING_SNAKE_CASE   :      set				     =       set()
	_construct_solution(_a							,			_a							,			_a							,			_a							,			_a)

	return optimal_val, example_optional_set

def  lowerCamelCase__ (					_a							,			_a							,			_a							,			_a							,			_a):
	# 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(_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__":
			a_						     =    [3, 2, 4, 4]
			a_						     =    [4, 3, 2, 3]
			a_						     =    4
			a_						     =    6
			a_						     =    [[0] * (w + 1)] + [[0] + [-1] * (w + 1) for _ in range(n + 1)]
			a_     ,	a_						     =    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
			a_     ,	a_						     =    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)