This assignment invites you to study, repair, and test a Python programs called
demonstrate-knapsack-solvers. The 0/1 Knapsack problem requires a computer program to determine which items to pick, from a list of items with both costs and benefits, in order to maximize the benefits while ensuring that the costs do not exceed a specified maximum cost. As part of this source code survey you will will implement and run three different greedy solvers called
greedy-by-value that vary in the way in which they select items. You will also implement and run an exhaustive 0/1 knapsack solver that is guaranteed to find the optimal solution for a specific problem instance. With that said, this exhaustive solver must generate the powerset of the set of all items and is thus only efficient for small knapsack instances. After running all three of the greedy solvers and then exhaustive solver you will be able to determine which greedy approach is best suited for the problem instance.
If you are a student enrolled in a Computer Science class at Allegheny College, you can access this assignment by clicking the link provided to you in Discord. Once you click this link it will create a GitHub repository that you can clone to your computer by following the general-purpose instructions in the description of the technical skills. Specifically, you will need to use the
git clone command to download the project from GitHub to your computer. Now you are ready to add source code and documentation to the project and then run the program to learn more about the efficiency and effectiveness trade-offs associated with different implementations of 0/1 knapsack solvers!
If you change into the
source/ directory of your GitHub repository, you will see one Python file called
demonstrate-knapsack-solvers module contains an incomplete class definition written as
class Item(object):. You need to follow the
TODO markers in this class definition, by inputting the source code from the text book, for functions like the constructor
def __init__(self, n, v, w) and like accessor functions such as
def get_name(self) -> str,
def get_value(self) -> int,
def get_weight(self) -> int. Since your textbook does not provide an implementation of a function for generating the powerset of a set, you will also need to consult the references in the source code and create your own function. Finally, you will need to implement the function that uses the generated powerset to perform an exhaustive search of all possible combinations of input.
To ensure that the
demonstrate-knapsack-solvers.py script analyzes the same instance of the 0/1 knapsack problem as is found in the textbook, you should use the following
build_items function that is also available in the provided source code. Lines
5 of this function respectively create the input to the knapsack solver that includes the name of the item and its value and weight (i.e., its cost). Lines
8 of this function populate the
List with all of the previously created instances of
Item. Finally, the
Item objects returned by this function on line
9 will be processed by both the greedy and exhaustive solvers.
1 2 3 4 5 6 7 8 9
After you have addressed all of the
TODO markers inside of the provided source code, you can run the program by typing the command
python demonstrate-knapsack-solvers.py as long as you have changed into the
source/ directory. If you correctly implemented the program and provided all of the source code required by the
TODO markers it should produce the following output. It is important to note that, at least for this instance of the 0/1 knapsack problem, the
greedy-by-density greedy solver produces the solution that is closest to the optimal one given by the exhaustive solver. It is important to note that, at least for this instance of the 0/1 knapsack problem, the
greedy-by-density solver produces the solution that is closest to the optimal one given by the exhaustive solver. Why do you think that this greedy solver produced the best solution? Do you think that it is always going to yield the best solution? Why or why not?
Running all of the knapsack solvers! Using greedy-by-value to fill knapsack of size 20 Total value of items taken is 200.0 (Computer, 200, 20) Using greedy-by-weight to fill knapsack of size 20 Total value of items taken is 170.0 (Book, 10, 1) (Vase, 50, 2) (Radio, 20, 4) (Painting, 90, 9) Using greedy-by-density to fill knapsack of size 20 Total value of items taken is 255.0 (Vase, 50, 2) (Clock, 175, 10) (Book, 10, 1) (Radio, 20, 4) Generating the powerset of all items! Using exhaustive enumeration to fill a knapsack of size 20 Total value of items taken is 275.0 (Clock, 175, 10) (Painting, 90, 9) (Book, 10, 1)
Since this project does not use Poetry to manage project dependencies and virtual environments, it does not support the use of commands like
poetry run task test. However, you can leverage the relevant instructions in the technical skills to run the command
gatorgrade --config config/gatorgrade.yml to check your work. If your work meets the baseline requirements and adheres to the best practices that proactive programmers adopt you will see that all the checks pass when you run
gatorgrade. You can study the
config/gatorgrade.yml file in your repository to learn how GatorGrade runs GatorGrader to automatically check your program and technical writing.
Did you know that GatorGrade and GatorGrader are open-source Python programs implemented by many proactive programmers? If you finish this source code survey and have extra time, please brainstorm some new features that you think these two tools should have, explain your idea by raising an issue in the relevant project's GitHub repository, and take the first step towards implementing and testing your idea. If the maintainers of these tools accept your new feature then you will have helped to improve the experience of other people who use GatorGrade and GatorGrader!
Once you have finished all of the previous technical tasks, you can use a text editor to answer all of the questions in the
writing/reflection.md file. Since this is a source code survey, you should provide output from running each of the provided Python programs on your own laptop and then explain how the program's source code produced that output. A specific goal for this project is to ensure that you can explain the behavior of the greedy solvers called
greedy-by-value. You should also be able to explain the trade-offs in terms of solution quality and efficiency of the knapsack solver that uses the exhaustive enumeration strategy.
Since this project is source code survey, it is aligned with the remembering and understanding levels of Bloom's taxonomy. You can learn more about how a proactive programming expert will assess your work by examining the assessment strategy. From the start to the end of this project you may make an unlimited number of reattempts at submitting source code and technical writing that meet the project's specification.
Emerging proactive programmers who have questions about this project are invited to ask them in either the GitHub discussions forum or the Proactive Programmers Discord server. Before you ask your question, please read the advice concerning how to best participate in the Proactive Programmers community. If you find a mistake in this project, please describe it and propose a solution by creating an issue in the GitHub Issue Tracker.