

Next:10.3.4
Bin PackingUp:10.3
Examples of some Intractable ProblemsPrevious: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