# Maximal

### From Glossary

In a partially ordered set, a maximal element is one for which no element follows it in the ordering. This is not to be confused with maximum. For example, consider the following knapsack problem:

The maximum value is , with
Define the partial
ordering to be the ordinary greater-than-or-equal-to, so that
means and
either or . In words, means we can put at
least one more item into the knapsack, in which case we would
increase our return. When we cannot do so, is a maximal
element. In particular, is a maximal element, and its value
is , which is *not* the maximum.

Another definition pertains to a subset with respect to some
property such that no proper superset has that property. In the 0-1
knapsack problem with variables, we define the subset of items
taken (for any solution) as Then, we
define as *maximal* if no item can be added without
violating the limit, i.e.,
for all not in