222 NONDETERMINISTIC ALGORITHMS
pack materials as efficiently as possible, and to the production of custom-
ordered pieces of some material that has to be cut from larger stock. For exam-
ple, if we have large sheets of metal and we have a bunch of orders for smaller
pieces of metal, we would obviously want to cut things as tightly as possible to
reduce waste and increase profits.■ 8.2.3 Backpack Problem^2
We have a set of objects that have different sizes, s 1 ,s 2 ,... , sN, and each of
these objects has a worth associated with it, w 1 ,w 2 ,... , wN. If we have a back-
pack of size K, the optimization problem determines the objects that we
should put in the backpack to maximize the total worth. As a decision prob-
lem, we would ask if there is a set of objects that will fit in the backpack and
have a total worth that is at least W.
This problem is related to investment strategies where the size of the objects
is the cost of various investments, the worths are the potential returns of those
investments, and the backpack size is the amount of capital available to invest.■ 8.2.4 Subset Sum Problem
We have a set of objects that have different sizes, s 1 ,s 2 ,... , sN, and we have
some positive upper limit L. The optimization version determines the subset of
the objects that produces the largest sum of sizes that is no greater than L. The
decision version would ask if there is a subset of the objects that has a total size
ofL. This is a simplified version of the backpack problem.■ 8.2.5 CNF-Satisfiability Problem
Conjunctive normal form (CNF) is a series of Boolean expressions that are all
combined by the AND operator (∧). Each of the individual expressions is a
series of Boolean variables combined with the OR operator (∨). A sample
CNF expression is (where represents “not x”)The CNF-satisfiability problem only has a decision version that asks if there
is some combination of true and false values for the variables so that the entire
equation is true. Because there is no limit on the number of variables or the(^2) The classic name for this problem is the Knapsack Problem.
x
()ab∨ ∧∧()ac∨ ()abcd∨∨∨∧()bcd∨∨ ∧()abcde∨∨∨∨