**Next:**10.3.3
Knapsack Problem**Up:**10.3
Examples of some Intractable Problems**Previous:**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