Knapsack

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.

JSON

{
  "Items": [
    {"ID": "cat",    "Value": 100, "Weight": 20},
    {"ID": "dog",    "Value":  20, "Weight": 45},
    {"ID": "water",  "Value":  40, "Weight":  2},
    {"ID": "phone",  "Value":   6, "Weight":  1},
    {"ID": "book",   "Value":  63, "Weight": 10},
    {"ID": "rx",     "Value":  81, "Weight":  1},
    {"ID": "tablet", "Value":  28, "Weight":  8},
    {"ID": "coat",   "Value":  44, "Weight":  9},
    {"ID": "laptop", "Value":  51, "Weight": 13},
    {"ID": "keys",   "Value":  92, "Weight":  1},
    {"ID": "nuts",   "Value":  18, "Weight":  4}
  ],
  "Capacity": 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.

type Knapsack struct {
    Capacity int    `json:"capacity"`
    Items    []Item `json:"items"`
}

The Item struct stores the id, value, and weight.

type Item struct {
    ID     string
    Value  int
    Weight int
}

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.

func main() {
    cli.Run(pack.Solver)
}

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.

func Solver(input schema.Knapsack, opt solve.Options) (solve.Solver, error) {
    root, err := root(input)
    if err != nil {
        return nil, err
    }

    return solve.Maximizer(root, opt), nil
}

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).

func root(input schema.Knapsack) (state, error) {
    // Sort items by descending quality.
    sort.Sort(sort.Reverse(schema.ByEfficiency(input.Items)))

    root := state{
        Knapsack: input,
        index:    -1,
    }

    // Add up all values and weights. These are naive maximums.
    for _, item := range root.Items {
        root.value.Upper += item.Value
        root.weight.Upper += item.Weight
    }

    return root, nil
}

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.

// Feasible is always true for this model.
func (s state) Feasible() bool {
    return true
}

// Value of the knapsack given the items it includes.
func (s state) Value() int {
    return s.value.Lower
}

// Bounds on the value of the knapsack. Items that are included only increase
// its value, which items that are excluded reduce its potential value.
func (s state) Bounds() model.Bounds {
    return s.value
}

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.

// Next adds the next item to the knapsack, or not.
func (s state) Next() model.Expander {
    if s.index >= len(s.Items)-1 {
        return nil
    }

    // Create knapsacks that exclude and include the next item.
    excluded := s.exclude()
    included := s.include()

    // We can always exclude items. Inclusion depends on capacity.
    next := []model.State{excluded}
    if included.weight.Lower <= included.Capacity {
        next = append(next, included)
    }
    return expand.Eager(next...)
}

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.

type state struct {
    schema.Knapsack

    value  model.Bounds
    weight model.Bounds

    index    int  // item index to consider
    included bool // true if the item is included in the knapsack
    parent   *state
}

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.

func (s state) exclude() state {
    index := s.index + 1
    return state{
        Knapsack: s.Knapsack,

        value:  s.value.TightenUpper(s.value.Upper - s.Items[index].Value),
        weight: s.weight.TightenUpper(s.weight.Upper - s.Items[index].Weight),

        index:    index,
        included: false,
        parent:   &s,
    }
}

func (s state) include() state {
    index := s.index + 1
    return state{
        Knapsack: s.Knapsack,

        value:  s.value.TightenLower(s.value.Lower + s.Items[index].Value),
        weight: s.weight.TightenLower(s.weight.Lower + s.Items[index].Weight),

        index:    index,
        included: true,
        parent:   &s,
    }
}

Output

We build our model into a binary and run it against our input data.

Bash

go build
./knapsack-cli \
    -hop.runner.output.solutions last \
    -hop.runner.input.path data/input.json \
    -hop.runner.output.path data/output.json

Our model gives us the following recommendation (written to stdout): Keep the cat. Leave the dog, tablet, and laptop at home. Pretty solid advice.

JSON

{
    "Contents": [
      {"ID": "keys",  "Value": 92,  "Weight": 1},
      {"ID": "rx",    "Value": 81,  "Weight": 1},
      {"ID": "water", "Value": 40,  "Weight": 2},
      {"ID": "book",  "Value": 63,  "Weight": 10},
      {"ID": "phone", "Value": 6,   "Weight": 1},
      {"ID": "cat",   "Value": 100, "Weight": 20},
      {"ID": "coat",  "Value": 44,  "Weight": 9},
      {"ID": "nuts",  "Value": 18,  "Weight": 4}
    ],
    "Weight": 48
  }

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.

Overview of the knapsack app.

Contents