The Knapsack Problem
Given a set of items with a weight and a value and given a knapsack with a maximum capacity, determine which items to include in the knapsack in order to maximise the total value inside it.
The Travelling Salesman Problem
Minimize the total distance traveled by the salesman while visiting all cities