Question

g You are looking to rob a jewelry store. You have been staking it out for a couple of weeks now and have learned the weights and values of every item in the store. You are looking to get the biggest score you possibly can but you are only one person and your backpack can only fit so much. Write a function called get_best_backpack(items: List[Item], max_capacity: int) -> "List[Item]" that accepts a list of Items as well as the maximum capacity that your backpack can hold and returns a list containing the most valuable items you can take that still fit in your backpack.

Answer 1

Answer:

A python code (Python recursion) was used for this given question

Explanation:

Solution

For this solution to the question, I am attaching code for these 2 files:

item.py

code.py

Source code for item.py:

class Item(object):

def __init__(self, name: str, weight: int, value: int) -> None:

  self.name = name

  self.weight = weight

  self.value = value

def __lt__(self, other: "Item"):

  if self.value == other.value:

if self.weight == other.weight:

  return self.name < other.name

else:

  return self.weight < other.weight

  else:

   return self.value < other.value

def __eq__(self, other: "Item") -> bool:

  if is instance(other, Item):

return (self.name == other.name and

self.value == other.value and

self.weight == other.weight)

  else:

return False

def __ne__(self, other: "Item") -> bool:

  return not (self == other)

def __str__(self) -> str:

  return f'A {self.name} worth {self.value} that weighs {self.weight}'

Source code for code.py:

#!/usr/bin/env python3

from typing import List

from typing import List, Generator

from item import Item

'''

Inductive definition of the function

fun3(0) is 5

fun3(1) is 7

fun3(2) is 11

func3(n) is fun3(n-1) + fun3(n-2) + fun3(n-3)

Solution 1: Straightforward but exponential

'''

def fun3_1(n: int) -> int:

result = None

if n == 0:

result = 5 # Base case

elif n == 1:

result = 7 # Base case

elif n == 2:

result = 11 # Base case

else:

result = fun3_1(n-1) + fun3_1(n-2) + fun3_1(n-3) # Recursive case

return result

''

Solution 2: New helper recursive function makes it linear

'''

def fun3(n: int) -> int:

''' Recursive core.

fun3(n) = _fun3(n-i, fun3(2+i), fun3(1+i), fun3(i))

'''

def fun3_helper_r(n: int, f_2: int, f_1: int, f_0: int):

result = None

if n == 0:

result = f_0 # Base case

elif n == 1:

result = f_1 # Base case

elif n == 2:

result = f_2 # Base case

else:

result = fun3_helper_r(n-1, f_2+f_1+f_0, f_2, f_1) # Recursive step

return result

return fun3_helper_r(n, 11, 7, 5)

''' binary_strings accepts a string of 0's, 1's, and X's and returns a generator that goes through all possible strings where the X's

could be either 0's or 1's. For example, with the string '0XX1',

the possible strings are '0001', '0011', '0101', and '0111'

'''

def binary_strings(string: str) -> Generator[str, None, None]:

def _binary_strings(string: str, binary_chars: List[str], idx: int):

if idx == len(string):

yield ''.join(binary_chars)

binary_chars = [' ']*len(string)

else:

char = string[idx]

if char != 'X':

binary_chars[idx]= char

yield from _binary_strings(string, binary_chars, idx+1)

else:

binary_chars[idx] = '0'

yield from _binary_strings(string, binary_chars, idx+1)

binary_chars[idx] = '1'

yield from _binary_strings(string, binary_chars, idx+1)

binary_chars = [' ']*len(string)

idx = 0

yield from _binary_strings(string, binary_chars, 0)

''' Recursive KnapSack: You are looking to rob a jewelry store. You have been staking it out for a couple of weeks now and have learned

the weights and values of every item in the store. You are looking to

get the biggest score you possibly can but you are only one person and

your backpack can only fit so much. Write a function that accepts a

list of items as well as the maximum capacity that your backpack can

hold and returns a list containing the most valuable items you can

take that still fit in your backpack. '''

def get_best_backpack(items: List[Item], max_capacity: int) -> List[Item]:

def get_best_r(took: List[Item], rest: List[Item], capacity: int) -> List[Item]:

if not rest or not capacity: # Base case

return took

else:

item = rest[0]

list1 = []

list1_val = 0

if item.weight <= capacity:

list1 = get_best_r(took+[item], rest[1:], capacity-item.weight)

list1_val = sum(x.value for x in list1)

list2 = get_best_r(took, rest[1:], capacity)

list2_val = sum(x.value for x in list2)

return list1 if list1_val > list2_val else list2

return get_best_r([], items, max_capacity)

Note: Kindly find an attached copy of the code outputs for python programming language below