1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
VARVARA [1.3K]
3 years ago
10

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 an

d 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.

Computers and Technology
1 answer:
ololo11 [35]3 years ago
5 0

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

You might be interested in
Mike is reading about machine-dependent programming languages. Which languages are machine-dependent programming languages?
Scilla [17]

Answer:

Assembly Language

Explanation:

Machine dependent is a language that only runs on specific machines. The early languages were machine-dependent while the advanced languages are machine-independent.

In the early languages, the main machine dependent language was machine language. Later on, Assembly language was introduced. Assembly language was also machine-dependent as it only runs on specific kinds of PCs.

8 0
3 years ago
Describe your ideas for a keyboarding game that would help someone improve their skills.
attashe74 [19]

Answer:

As you prepare to enter the workforce, here are some pointers to improve your own typing skills:

1.) Use the correct starting position. ...

2.) Don't look down your hands. ...

3.) Maintain good posture. ...

4.) Find a comfortable position for your hands. ...

5.) Practice!

5 0
3 years ago
Help !!!!!
viva [34]
I believe it’s D because software is the programs and other operations used by a computer
3 0
3 years ago
Select the correct answer.
ale4655 [162]

Answer:

I think it's B

Explanation:

6 0
2 years ago
Read 2 more answers
What is an electronic tool that stores large amounts of data in one place in a systematic, logical way? A Database B Platform C
ohaa [14]

Answer:

Database: An integrated collection of logically related records or files. A database consolidates records previously stored in separate files into a common pool of data records that provides data for many applications. The data is managed by systems software called database management systems (DBMS). The data stored in a database is independent of the application programs using it and of the types of secondary storage devices on which it is stored.

4 0
3 years ago
Other questions:
  • Whats the difference between copying a file to my desktop and creating a shortcut?
    8·1 answer
  • Convert the following pseudi code to C++ code. BE sure to define the apprpriat evariables.
    9·1 answer
  • ____ is a utility that can verify that TCP/IP is installed, bound to the NIC, configured correctly, and communicating with the n
    11·1 answer
  • What is the name of the most expensive car and how much is it and what are its features
    15·1 answer
  • _____ are independent and not associated with the marketing efforts of any particular company or brand.​
    9·1 answer
  • What would a digitizing application create?
    13·2 answers
  • Select the correct word to complete the sentence
    11·2 answers
  • What are the data type(s) will be used to declare the variable(s) needed to
    9·1 answer
  • Suppose in an Excel spreadsheet, the value in cell A1 is 25. By using the Macabacus local currency cycle shortcuts (Ctrl + Shift
    10·1 answer
  • According to behaviorism, instruction should provide necessary stimulus in order for
    8·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!