This page is deprecated as of Hop v0.7.0.
Knapsack is a classic combinatorial optimization problem. Given a collection of items with a value and weight, our objective is to maximize the total value without exceeding the weight capacity of the knapsack.
Input
Say we have the following input data for our knapsack problem in a file input.json
. Cats are heavy but highly prized. Dogs are heavier and less valuable. The remaining items have value and weight estimates assigned to them as well. Our knapsack's capacity is a weight of 50.
The schema
package
In our schema package, we have defined the structure of our knapsack
. A knapsack
consists of a capacity and an array of type Item
.
The Item
struct stores the id, value, and weight.
The main
package
In the main
package, the main
function acts as the entry point into our model. Within this function we have defined our runner, in this case it has been configured to run from the command-line. Other runners are available, more information can be found in the Deployment overview section of our documentation.
The pack
package
Root State
Solver
takes the input and option flags provided by the runner defined in main.go
. It then initializes the root state of the model, and returns a solver that maximizes the objective.
root
sorts the items by descending efficiency. In this case, efficiency is defined as the ratio of value to weight. It should be noted that sorting provides a significant performance improvement when considering larger pools of items (anywhere from 40 to 10,000).
Pack Model
The Feasible
, Value
, and Bounds
methods are all fairly simple. A state is feasible once we have iterated over each item and assigned a boolean value to included.
We compute both the value and the maximum value of each state when we construct them.
One important item to note is that we take the lower bound of the Value.
Here, upper bound represents how much I could potentially put into my knapsack based on what's left to evaluate. The lower bound is what is actually in the knapsack and thus the value we want to compare between improving solutions.
Our Next
method constructs two new states. Each one makes a decision about the next item to consider. If including that item produces a state that exceeds our weight limit, then we do not return it.
System state
The struct for our state
is fairly straightforward. state
embeds the Knapsack
, and stores value
, weight
, and index
of each item. Both value
and weight
are model.IntRange
types. Each item has a boolean value indicating whether it is included (true) or excluded (false). Note that we only have a single copy of each item to include. So while packing multiple cats may sound like a brilliant idea, we can only pack the one.
Finally, we have methods for creating new states based on the decision to exclude or include the next item. Excluding an item reduces the maximum value of the new state and does not increase its weight. Including an item increases the weight and adds value to the knapsack.
Output
We build our model into a binary and run it against our input data.
Our model gives us the following recommendation (written to stdout): Keep the cat. Leave the dog, tablet, and laptop at home. Pretty solid advice.
Profiling Models
Once you start building your own Hop model, you'll want to be sure and run a CPU profiler to better understand performance. Visit the section on profiling to learn more about profiling. You can always use an example like this one to test concepts.