Babbage needs your help filling up his bookbag with valuable items!
Problem: Identify the subset of items that will maximize their value while keeping their total weight equal to or below a threshold.
Input: The filename of a local file containing a sequence of items, each on their own line.
The first line contains the number of total items in the facility.
The second line specifies the maximum
capacity of the bookbag.
All subsequent lines describe the sequence of items and contain three elements.
An item’s information consists of the following information, separated by spaces:
nameof the item, without spaces and no more than 256 characters long.
weightof the item
valueof the item
An example input file is below:
5 15 Blueprints 4 50 HardDrive 10 2 DogFood 10 5 MysteriousCrystal 20 60 SuperComputer 100 100
Output: The name of each chosen item on its own line, with the last line having the total value of the items.
An example of output is below:
Blueprints DogFood 55
A critical aspect of this Problem is to understand that Babbage can only carry a certain amount of total weight.
We call this total weight the
capacity of the bookbag. In the example above, the
capacity is 15. This means
that we can take:
Blueprints, which weigh 4
DogFood, which weigh 10
The total weight of these objects is 14, and their total value is 55. Notice that we take the
HardDrive, because Babbage believes the
DogFood is worth more (I mean, he is a dog).
The other two options cannot be considered because their weight is more than the capacity of the bag.
However, if the
capacity was instead 20, then the output would be:
The increased capacity means Babbage can now carry the
MysteriousCrystal, which has a value of 60 and a weight of 20.
This is more than the combined value of the
DogFood, so he leaves them behind.
Your solution must work in time complexity
n is the number of items and
W is the numerical size of the capacity.
W term - we are asking for pseudo-polynomial time algorithm.
You will be submitting this assignment through GradeScope. The same rules will apply for all coding assignments in this course, so you should read them all carefully: GradeScope Instructions
Critically, this is an individual assignment. Do not share code with any of your group mates!
For this project, you will need to create an
answer.py that solves the problem above, a
explains your solution at a high level, and a
test.py that tests your solution in some way.
readme.md file, make sure you clearly explain the algorithmic runtime of your program in terms of Big O.
For full credit, you must be able to justify your program’s complexity as worst case
All parts of your solution, including both the program and the
readme.md file should be submitted on GradeScope: https://www.gradescope.com/courses/230699/assignments/1189387/
You will be graded on the following components:
readme.mdfile of the algorithmic runtime of your program.
Note that unclear code and answers can cause a huge penalty to your grade. We are not being strict on coding style, but we shouldn’t have to run your code through a deobfuscator to figure out what it does. You might also lose points if you ignore instructions in this assignment, or bypass the autograder, even if the autograder gives you points.