Visualizing the knapsack problem

The code for the knapsack problem has been provided in this book’s GitHub repository. This initial part of the code sets up a sample knapsack problem and then solves it using a probabilistic method. Other classical methods are available and have been mentioned in the Further reading section.

First, let’s explain how the plot_knapsack() function works. This function tries adding the items in a variety of ways, starting with one-item combinations, then two-item combinations, and then tracks the maximum value and weight found. It will do this until it reaches the total number of items. While sampling, it will print the solution (items, value, and weight) if the value exceeds the previously stored maximum value. The plots show all the combinations it finds. The X-axis is the sample number (not the number of items in the solution).

Now, let’s set up and run through a sample knapsack problem. The data of the value and the weight...