(knapsack = backpack, bag)

A burglar breaks into a house and wants to steal. But the capacity of the knapsack is limited. They need to get the most valuable out of the robbery but it still needs to fit.

Continuous (fractional) knapsack problem

You can take pieces of an object. This problem is easy to solve, with a greedy algorithm. You take the best thing first as long as you can.

0/1 knapsack problem

You either take the object or you don’t. More complicated because making a decision impacts future decisions. A greedy algorithm is not guaranteed to give the best answer.

Each item is represented by a pair .

The knapsack can accomodate items with a total weight no more than .

A vector of length represents the set of available items.

A vector of length is used to indicate wether an item is taken or not. means that item is taken.

A binary number can represent the items to take, using a single vector of zeroes and ones.

Find that maximizes:

(sum of the taken values)

subject to the constraint that:

(sum of the taken weights is less or equal than the capacity)