The knapsack problem

Input: The volume $v$ of a knapsack and the volumes and values of a collection of zero or more objects.
Output: A list of zero or more objects that are to be placed in the knapsack.

More realistic than the trivial knapsack problem we previously introduced is the actual knapsack problem: given a knapsack that has a given volume $v$, and given $m$ objects, each of which has both a given volume and value, the knapsack problem has you find that combination of objects that can be held by the knapsack while maximizing the total value of the objects in the knapsack.

The trivial knapsack problem described before is equivalent to the knapsack problem when the value of each object is proportional to its volume.

The multi-constraint knapsack problem

Input: The volume $v$ and mass-bearing capacity $m$ of a knapsack and the volumes, masses and values of a collection of zero or more objects.
Output: A list of zero or more objects that are to be placed in the knapsack.

Even more realistically, a knapsack has a volume, but it also has a maximum weight it can hold. Thus, given a knapsack that holds $n$ liters and can hold a mass of $w$ kilograms, and given $m$ objects, each with a given volume and mass and a value, what is the optimal collection of objects that can be placed into the knapsack that maximizes the value while not exceeding either the volume or the mass the knapsack is capable of holding.

You can read more about this problem at Wikipedia and Steven Skiena's algorithm repository.