Imagine that you are going to a trip, and everything you have just a knapsack to carry on everything.

The maximum weight you can carry is limited, say 14 kg.

There are a list of itens you’re considering to choose from. Each item has a weight and a value.

Which of the itens do I choose, to maximize the value I can carry on my backpack?

**The “Human method”**

The first method described is the “human method”. How you and me would choose the itens.

I would choose the itens with greatest value for me, one by one, till the maximum weight.

In this example, I would choose itens 1 and 2, whose sum of values is 13.000 and sum of weights is 14. It is the “greedy” method, heuristically simple but can be suboptimal.

In the end, I would take a look on my selection, and try to find if I can replace one of the chosen itens for two itens not choosed with greater value.

In this example, a simple inspection shows that the item 2 is too heavy for its benefits. It is better to replace it for itens 3 and 4.

The final selection contains itens {1, 3, 4}, with total value 14.000 (10.000 + 2000 + 2000) and weight 13 (8 +2+3).

The problem is when the list is very large, with tens or hundreds of itens. It is several timer harder to figure out a good solution.

The human method is very important. It is suboptimal, but it is fast.

**Humans are good problem solvers**. We use intuition and millions of years of understanding of nature, to solve this kind of problem. Human reasoning can be a source for fast approximation algorithms.Even when the problem is large, humans can solve in a heuristically interesting way. The world is also

**Pareto**, what means that 20% of itens will have 80% of the value. In a intuitive way, I would focus my attention in those 20% and apply the above described method.In real world application problems, I always respect a lot the people who make the analysis and try to someway incorporate some of theirs thinking in my models – a human centered analytics.

**Mathematical formulation**

The formulation of the knapsack problem via integer programming is straightforward.

If xi is the decision variable, binary (1 is to carry the item, 0 is to not carry) then

In the next posts I’ll show how to solve it with computational methods, as dynamic programming, integer programming using solver and evolutive metaheuristics.

Arnaldo Gunzi

A big fan of real world heuristics

Advertisements

## One thought on “The knapsack problem”