The subset-sum problem is one of the most frequently occurring NP (nondeterministic, polynomi-al-time)-complete) problems. It asks whether a subset of numbers in a set of positive integers adds up exactly to a given value. A relaxed version of the problem tries to identify a subset of numbers that adds up to a maximum value no greater than a given value. This problem arises in transportation, network design, scheduling, logistics systems, robotics, and many other areas. The problem permits you to develop and illustrate the power of different algorithmic tools.
展开▼