Next:10.3.3 Knapsack ProblemUp:10.3 Examples of some Intractable ProblemsPrevious:10.3.1 Traveling Salesman Problem

10.3.2 Subset Sum

The input is a positive integer C and n objects whose sizes are positive integers s1, s2,..., sn.

Optimization Problem: Among all subsets of objects with sum at most C, what is the largest subset sum?

Decision Problem: Is there a subset of objects whose sizes add up to exactly C?