You have before you a shelf of items and a knapsack to put them in.
Each item as a weight (the number of squares in its image or the weight label), and a value in dollars.
Your knapsack has a maximum weight (determined by the "Max Weight" input at the bottom of the page).
Your goal is to take things from the shelf and put them in your knapsack such that you maximize the value of your knapsack without going over the maximum.
Left Click on a Shelf Item to put it in your Knapsack, Left Click on a Knapsack Item to put it back on the Shelf
On the right side of the page there is the memoization table for your shelf.
Once you know what that is and how to use it, it might help you fill your knapsack...
Shelf:
Knapsack:
The Knapsack problem is a problem solved by dynamic programming!
This is similar to the divide-and-conquer approach, but it also includes memoization.
What is memoization? It's basically storing solutions to subproblems that we're going to repeat so that we don't have to repeat the same calculation over and over again. This saves on running time.
For the knapsack problem, we have a limited weight in our knapsack, but we want to maximize the value of items we select. In the table, we either have the choice of including an item or not including it, depending on if it will fit within the weight limits, and we calculate the maximum value from those choices.
Here is a great explanation of how this works!