
import math
import unittest

from transformers import BioGptConfig, is_torch_available
from transformers.testing_utils import require_torch, slow, torch_device

from ...generation.test_utils import GenerationTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
	import torch

	from transformers import (
	    BioGptForCausalLM,
	    BioGptForSequenceClassification,
	    BioGptForTokenClassification,
	    BioGptModel,
	    BioGptTokenizer,
	)
	from transformers.models.biogpt.modeling_biogpt import BIOGPT_PRETRAINED_MODEL_ARCHIVE_LIST







class        A_   :




	'''simple docstring'''


	def __init__(       self		,    snake_case		,    snake_case=13		,    snake_case=7		,    snake_case=True		,    snake_case=True		,    snake_case=False		,    snake_case=True		,    snake_case=99		,    snake_case=32		,    snake_case=5		,    snake_case=4		,    snake_case=37		,    snake_case="gelu"		,    snake_case=0.1		,    snake_case=0.1		,    snake_case=512		,    snake_case=16		,    snake_case=2		,    snake_case=0.02		,    snake_case=3		,    snake_case=4		,    snake_case=None		,    ):
		lowercase       =    parent
		lowercase       =    batch_size
		lowercase       =    seq_length
		lowercase       =    is_training
		lowercase       =    use_input_mask
		lowercase       =    use_token_type_ids
		lowercase       =    use_labels
		lowercase       =    vocab_size
		lowercase       =    hidden_size
		lowercase       =    num_hidden_layers
		lowercase       =    num_attention_heads
		lowercase       =    intermediate_size
		lowercase       =    hidden_act
		lowercase       =    hidden_dropout_prob
		lowercase       =    attention_probs_dropout_prob
		lowercase       =    max_position_embeddings
		lowercase       =    type_vocab_size
		lowercase       =    type_sequence_label_size
		lowercase       =    initializer_range
		lowercase       =    num_labels
		lowercase       =    num_choices
		lowercase       =    scope





	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		lowercase       =    ids_tensor([self.batch_size, self.seq_length]		,    self.vocab_size       )

		lowercase       =    None
		if self.use_input_mask:
			lowercase       =    random_attention_mask([self.batch_size, self.seq_length]       )

		lowercase       =    None
		if self.use_token_type_ids:
			lowercase       =    ids_tensor([self.batch_size, self.seq_length]		,    self.type_vocab_size       )

		lowercase       =    None
		lowercase       =    None
		lowercase       =    None
		if self.use_labels:
			lowercase       =    ids_tensor([self.batch_size]		,    self.type_sequence_label_size       )
			lowercase       =    ids_tensor([self.batch_size, self.seq_length]		,    self.num_labels       )
			lowercase       =    ids_tensor([self.batch_size]		,    self.num_choices       )

		lowercase       =    self.get_config()

		return config, input_ids, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels





	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		return BioGptConfig(
		    vocab_size=self.vocab_size		,    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		,    max_position_embeddings=self.max_position_embeddings		,    type_vocab_size=self.type_vocab_size		,    is_decoder=snake_case		,    initializer_range=self.initializer_range		,    )





	def 	SCREAMING_SNAKE_CASE__						(       self		,    snake_case		,    snake_case		,    snake_case		,    snake_case		,    snake_case		,    snake_case		,    snake_case       ):
		lowercase       =    BioGptModel(config=snake_case       )
		model.to(snake_case       )
		model.eval()
		lowercase       =    model(snake_case		,    attention_mask=snake_case       )
		lowercase       =    model(snake_case       )
		self.parent.assertEqual(result.last_hidden_state.shape		,    (self.batch_size, self.seq_length, self.hidden_size)       )





	def 	SCREAMING_SNAKE_CASE__						(       self		,    snake_case		,    snake_case		,    snake_case		,    snake_case		,    snake_case		,    snake_case		,    snake_case		,    snake_case		,    snake_case		,    ):
		lowercase       =    BioGptForCausalLM(config=snake_case       )
		model.to(snake_case       )
		model.eval()
		lowercase       =    model(snake_case		,    attention_mask=snake_case		,    token_type_ids=snake_case		,    labels=snake_case       )
		self.parent.assertEqual(result.logits.shape		,    (self.batch_size, self.seq_length, self.vocab_size)       )





	def 	SCREAMING_SNAKE_CASE__						(       self		,    snake_case		,    snake_case		,    snake_case		,    snake_case		,    snake_case		,    *snake_case       ):
		lowercase       =    BioGptModel(config=snake_case       )
		model.to(snake_case       )
		model.eval()

		# create attention mask
		lowercase       =    torch.ones(input_ids.shape		,    dtype=torch.long		,    device=snake_case       )
		lowercase       =    self.seq_length // 2
		lowercase       =    0

		# first forward pass
		lowercase  ,					lowercase       =    model(snake_case		,    attention_mask=snake_case       ).to_tuple()

		# create hypothetical next token and extent to next_input_ids
		lowercase       =    ids_tensor((self.batch_size, 1)		,    config.vocab_size       )

		# change a random masked slice from input_ids
		lowercase       =    ids_tensor((1,)		,    snake_case       ).item() + 1
		lowercase       =    ids_tensor((self.batch_size, 1)		,    config.vocab_size       ).squeeze(-1       )
		lowercase       =    random_other_next_tokens

		# append to next input_ids and attn_mask
		lowercase       =    torch.cat([input_ids, next_tokens]		,    dim=-1       )
		lowercase       =    torch.cat(
		    [attn_mask, torch.ones((attn_mask.shape[0], 1)		,    dtype=torch.long		,    device=snake_case       )]		,    dim=1		,    )

		# get two different outputs
		lowercase       =    model(snake_case		,    attention_mask=snake_case       )['last_hidden_state']
		lowercase       =    model(snake_case		,    past_key_values=snake_case		,    attention_mask=snake_case       )['last_hidden_state']

		# select random slice
		lowercase       =    ids_tensor((1,)		,    output_from_past.shape[-1]       ).item()
		lowercase       =    output_from_no_past[:, -1, random_slice_idx].detach()
		lowercase       =    output_from_past[:, 0, random_slice_idx].detach()

		# test that outputs are equal for slice
		self.parent.assertTrue(torch.allclose(snake_case		,    snake_case		,    atol=1E-3       )       )





	def 	SCREAMING_SNAKE_CASE__						(       self		,    snake_case		,    snake_case		,    snake_case		,    snake_case		,    snake_case		,    *snake_case       ):
		lowercase       =    BioGptModel(config=snake_case       ).to(snake_case       ).eval()

		lowercase       =    torch.ones(input_ids.shape		,    dtype=torch.long		,    device=snake_case       )

		# first forward pass
		lowercase       =    model(snake_case		,    attention_mask=snake_case		,    use_cache=snake_case       )

		lowercase  ,					lowercase       =    outputs.to_tuple()

		# create hypothetical multiple next token and extent to next_input_ids
		lowercase       =    ids_tensor((self.batch_size, 3)		,    config.vocab_size       )
		lowercase       =    ids_tensor((self.batch_size, 3)		,    2       )

		# append to next input_ids and
		lowercase       =    torch.cat([input_ids, next_tokens]		,    dim=-1       )
		lowercase       =    torch.cat([attention_mask, next_attn_mask]		,    dim=-1       )

		lowercase       =    model(snake_case		,    attention_mask=snake_case       )['last_hidden_state']
		lowercase       =    model(snake_case		,    attention_mask=snake_case		,    past_key_values=snake_case       )[
		    'last_hidden_state'
		]

		# select random slice
		lowercase       =    ids_tensor((1,)		,    output_from_past.shape[-1]       ).item()
		lowercase       =    output_from_no_past[:, -3:, random_slice_idx].detach()
		lowercase       =    output_from_past[:, :, random_slice_idx].detach()

		self.parent.assertTrue(output_from_past_slice.shape[1] == next_tokens.shape[1]       )

		# test that outputs are equal for slice
		self.parent.assertTrue(torch.allclose(snake_case		,    snake_case		,    atol=1E-3       )       )





	def 	SCREAMING_SNAKE_CASE__						(       self		,    snake_case		,    snake_case		,    snake_case		,    snake_case		,    snake_case		,    *snake_case		,    snake_case=False       ):
		lowercase       =    BioGptForCausalLM(snake_case       )
		model.to(snake_case       )
		if gradient_checkpointing:
			model.gradient_checkpointing_enable()

		lowercase       =    model(snake_case		,    labels=snake_case       )
		self.parent.assertEqual(result.loss.shape		,    ()       )
		self.parent.assertEqual(result.logits.shape		,    (self.batch_size, self.seq_length, self.vocab_size)       )
		result.loss.backward()





	def 	SCREAMING_SNAKE_CASE__						(       self		,    snake_case		,    *snake_case       ):
		lowercase       =    BioGptModel(snake_case       )
		lowercase       =    model.config.initializer_range / math.sqrt(2 * model.config.num_hidden_layers       )
		for key in model.state_dict().keys():
			if "c_proj" in key and "weight" in key:
				self.parent.assertLessEqual(abs(torch.std(model.state_dict()[key]       ) - model_std       )		,    0.001       )
				self.parent.assertLessEqual(abs(torch.mean(model.state_dict()[key]       ) - 0.0       )		,    0.01       )





	def 	SCREAMING_SNAKE_CASE__						(       self		,    snake_case		,    snake_case		,    snake_case		,    snake_case		,    snake_case		,    *snake_case       ):
		lowercase       =    self.num_labels
		lowercase       =    BioGptForTokenClassification(snake_case       )
		model.to(snake_case       )
		model.eval()
		lowercase       =    model(snake_case		,    attention_mask=snake_case		,    token_type_ids=snake_case       )
		self.parent.assertEqual(result.logits.shape		,    (self.batch_size, self.seq_length, self.num_labels)       )





	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		lowercase       =    self.prepare_config_and_inputs()
		(
		    (
		    lowercase
		)  ,					(
		    lowercase
		)  ,					(
		    lowercase
		)  ,					(
		    lowercase
		)  ,					(
		    lowercase
		)  ,					(
		    lowercase
		)  ,					(
		    lowercase
		)  ,					
		)       =    config_and_inputs
		lowercase       =    {'input_ids': input_ids, 'attention_mask': input_mask}
		return config, inputs_dict







@require_torch
class        A_   (			__lowerCamelCase      ,	__lowerCamelCase      ,	__lowerCamelCase      ,	unittest.TestCase   ):




	'''simple docstring'''


	_UpperCamelCase     :     str							 =       (
	    (BioGptModel, BioGptForCausalLM, BioGptForSequenceClassification, BioGptForTokenClassification)
	    if is_torch_available()
	    else ()
	)
	_UpperCamelCase     :     Optional[int]							 =       (BioGptForCausalLM,) if is_torch_available() else ()
	_UpperCamelCase     :     Dict							 =       (
	    {
	        """feature-extraction""": BioGptModel,
	        """text-classification""": BioGptForSequenceClassification,
	        """text-generation""": BioGptForCausalLM,
	        """token-classification""": BioGptForTokenClassification,
	        """zero-shot""": BioGptForSequenceClassification,
	    }
	    if is_torch_available()
	    else {}
	)
	_UpperCamelCase     :     int							 =       False





	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		lowercase       =    BioGptModelTester(self       )
		lowercase       =    ConfigTester(self		,    config_class=snake_case		,    hidden_size=37       )





	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		self.config_tester.run_common_tests()





	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		lowercase       =    self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_model(*snake_case       )





	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		lowercase       =    self.model_tester.prepare_config_and_inputs()
		for type in ["absolute", "relative_key", "relative_key_query"]:
			lowercase       =    type
			self.model_tester.create_and_check_model(*snake_case       )





	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		lowercase       =    self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_biogpt_model_attention_mask_past(*snake_case       )





	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		lowercase       =    self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_forward_and_backwards(*snake_case		,    gradient_checkpointing=snake_case       )





	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		lowercase       =    self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_biogpt_model_past_large_inputs(*snake_case       )





	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		lowercase       =    self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_biogpt_weight_initialization(*snake_case       )





	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		lowercase       =    self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_biogpt_for_token_classification(*snake_case       )





	@slow
	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		lowercase       =    BioGptForCausalLM.from_pretrained('microsoft/biogpt'       )
		model.to(snake_case       )
		lowercase       =    BioGptTokenizer.from_pretrained('microsoft/biogpt'       )

		lowercase       =    'left'

		# Define PAD Token = EOS Token = 50256
		lowercase       =    tokenizer.eos_token
		lowercase       =    model.config.eos_token_id

		# use different length sentences to test batching
		lowercase       =    [
		    'Hello, my dog is a little',
		    'Today, I',
		]

		lowercase       =    tokenizer(snake_case		,    return_tensors='pt'		,    padding=snake_case       )
		lowercase       =    inputs['input_ids'].to(snake_case       )

		lowercase       =    model.generate(
		    input_ids=snake_case		,    attention_mask=inputs['attention_mask'].to(snake_case       )		,    )

		lowercase       =    tokenizer(sentences[0]		,    return_tensors='pt'       ).input_ids.to(snake_case       )
		lowercase       =    model.generate(input_ids=snake_case       )

		lowercase       =    inputs_non_padded.shape[-1] - inputs['attention_mask'][-1].long().sum().cpu().item()
		lowercase       =    tokenizer(sentences[1]		,    return_tensors='pt'       ).input_ids.to(snake_case       )
		lowercase       =    model.generate(input_ids=snake_case		,    max_length=model.config.max_length - num_paddings       )

		lowercase       =    tokenizer.batch_decode(snake_case		,    skip_special_tokens=snake_case       )
		lowercase       =    tokenizer.decode(output_non_padded[0]		,    skip_special_tokens=snake_case       )
		lowercase       =    tokenizer.decode(output_padded[0]		,    skip_special_tokens=snake_case       )

		lowercase       =    [
		    'Hello, my dog is a little bit bigger than a little bit.',
		    'Today, I have a good idea of how to use the information',
		]
		self.assertListEqual(snake_case		,    snake_case       )
		self.assertListEqual(snake_case		,    [non_padded_sentence, padded_sentence]       )





	@slow
	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		for model_name in BIOGPT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
			lowercase       =    BioGptModel.from_pretrained(snake_case       )
			self.assertIsNotNone(snake_case       )





	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		lowercase  ,					lowercase       =    self.model_tester.prepare_config_and_inputs_for_common()
		lowercase       =    3
		lowercase       =    input_dict['input_ids']
		lowercase       =    input_ids.ne(1       ).to(snake_case       )
		lowercase       =    ids_tensor([self.model_tester.batch_size]		,    self.model_tester.type_sequence_label_size       )
		lowercase       =    BioGptForSequenceClassification(snake_case       )
		model.to(snake_case       )
		model.eval()
		lowercase       =    model(snake_case		,    attention_mask=snake_case		,    labels=snake_case       )
		self.assertEqual(result.logits.shape		,    (self.model_tester.batch_size, self.model_tester.num_labels)       )





	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		lowercase  ,					lowercase       =    self.model_tester.prepare_config_and_inputs_for_common()
		lowercase       =    3
		lowercase       =    'multi_label_classification'
		lowercase       =    input_dict['input_ids']
		lowercase       =    input_ids.ne(1       ).to(snake_case       )
		lowercase       =    ids_tensor(
		    [self.model_tester.batch_size, config.num_labels]		,    self.model_tester.type_sequence_label_size       ).to(torch.float       )
		lowercase       =    BioGptForSequenceClassification(snake_case       )
		model.to(snake_case       )
		model.eval()
		lowercase       =    model(snake_case		,    attention_mask=snake_case		,    labels=snake_case       )
		self.assertEqual(result.logits.shape		,    (self.model_tester.batch_size, self.model_tester.num_labels)       )







@require_torch
class        A_   (			unittest.TestCase   ):




	'''simple docstring'''


	@slow
	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		lowercase       =    BioGptForCausalLM.from_pretrained('microsoft/biogpt'       )
		lowercase       =    torch.tensor([[2, 4805, 9, 656, 21]]       )
		lowercase       =    model(snake_case       )[0]

		lowercase       =    4_2384

		lowercase       =    torch.Size((1, 5, vocab_size)       )
		self.assertEqual(output.shape		,    snake_case       )

		lowercase       =    torch.tensor(
		    [[[-9.5_236, -9.8_918, 10.4_557], [-11.0_469, -9.6_423, 8.1_022], [-8.8_664, -7.8_826, 5.5_325]]]       )

		self.assertTrue(torch.allclose(output[:, :3, :3]		,    snake_case		,    atol=1E-4       )       )





	@slow
	def 	SCREAMING_SNAKE_CASE__						(       self       ):
		lowercase       =    BioGptTokenizer.from_pretrained('microsoft/biogpt'       )
		lowercase       =    BioGptForCausalLM.from_pretrained('microsoft/biogpt'       )
		model.to(snake_case       )

		torch.manual_seed(0       )
		lowercase       =    tokenizer('COVID-19 is'		,    return_tensors='pt'       ).to(snake_case       )
		lowercase       =    model.generate(
		    **snake_case		,    min_length=100		,    max_length=1024		,    num_beams=5		,    early_stopping=snake_case		,    )
		lowercase       =    tokenizer.decode(output_ids[0]		,    skip_special_tokens=snake_case       )

		lowercase       =    (
		    'COVID-19 is a global pandemic caused by severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2), the'
		    ' causative agent of coronavirus disease 2019 (COVID-19), which has spread to more than 200 countries and'
		    ' territories, including the United States (US), Canada, Australia, New Zealand, the United Kingdom (UK),'
		    ' and the United States of America (USA), as of March 11, 2020, with more than 800,000 confirmed cases and'
		    ' more than 800,000 deaths.'
		)
		self.assertEqual(snake_case		,    snake_case       )



def 							UpperCAmelCase_		(							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE							):
	global f  # a global dp table for knapsack
	if f[i][j] < 0:
		if j < wt[i - 1]:
			lowercase       =    mf_knapsack(i - 1 ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE							)
		else:
			lowercase       =    max(
			    mf_knapsack(i - 1 ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE							) ,							mf_knapsack(i - 1 ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							j - wt[i - 1]							) + val[i - 1] ,							)
		lowercase       =    val
	return f[i][j]






def 							UpperCAmelCase_		(							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE							):
	lowercase       =    [[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_:
				lowercase       =    max(val[i - 1] + dp[i - 1][w_ - wt[i - 1]] ,							dp[i - 1][w_]							)
			else:
				lowercase       =    dp[i - 1][w_]

	return dp[n][w_], dp






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

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

	lowercase  ,					lowercase       =    knapsack(__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE							)
	lowercase       =    set()
	_construct_solution(__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE							)

	return optimal_val, example_optional_set






def 							UpperCAmelCase_		(							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE							):
	# 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(__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							i - 1 ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE							)
		else:
			optimal_set.add(__SCREAMING_SNAKE_CASE							)
			_construct_solution(__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							i - 1 ,							j - wt[i - 1] ,							__SCREAMING_SNAKE_CASE							)


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

