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?