Variations of the 0/1 Knapsack Problem

In this chapter, we will look at several variations of the 0/1 knapsack problem. As we will see, they mostly revolve around questions involving properties of subsets subject to a knapsack constraint. We will examine the following variations:

• Subset sum, can we find a subset whose items sum to a certain value
• Existence of integer partitions
  • Subsets that sum to the same value
  • Subsets that minimize their difference
• Counting subsets