Knapsack

We want to decide which elements to put inside a bag in order to maximize the total value of the contents while respecting the capacity of said bag.

Name of the dag: knapsack

Available solution methods:

• Dynamic: a dynamic programming approach.

• Direct: a direct heuristic approach.

• Random: a random heuristic approach.

• MIP: a mixed integer programming approach.

Decision

A list of items to put inside the bag.

Parameters

• Items: the weight and the value for each item.

• Capacity of the bag.