Examples of some Intractable ProblemsPrevious:10.3.2
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,
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?