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?
eEL,CSA_Dept,IISc,Bangalore