**Next:**10.3.4
Bin Packing**Up:**10.3
Examples of some Intractable Problems**Previous:**10.3.2
Subset Sum

##
10.3.3 Knapsack Problem

This is a generalization of the subset sum problem. Consider a knapsack
of capacity *C* where *C* is a positive integer and *n*
objects with positive integer sizes *s1,
s2,..., sn* and positive integer profits *p1,
p2,..., pn.*
Optimization Problem: Find the largest total profit of any subset of
the objects that fits in the knapsack.

Decision Problem: Given *k*, is there a subset of the objects that
fits in the knapsack and has total profit at least *k*?

eEL,CSA_Dept,IISc,Bangalore