List of Knapsack Problems - Knapsack-like Problems

Knapsack-like Problems

If all the profits are 1, we can try to minimize the number of items which exactly fill the knapsack:

If we have a number of containers (of the same size), and we wish to pack all n items in as few containers as possible, we get the bin packing problem, which is modelled by having indicator variables container i is being used:

The cutting stock problem is identical to the bin packing problem, but since practical instances usually have far fewer types of items, another formulation is often used. Item j is needed B_j times, each "pattern" of items which fit into a single knapsack have a variable, x_i (there are m patterns), and pattern i uses item j b_ij times:

If, to the multiple choice knapsack problem, we add the constraint that each subset is of size n and remove the restriction on total weight, we get the assignment problem, which is also the problem of finding a maximal bipartite matching:

In the Maximum Density Knapsack variant there is an initial weight, and we maximize the density of selected of items which do not violate the capacity constraint:

Although less common than those above, several other knapsack-like problems exist, including:

• Nested knapsack problem
• Collapsing knapsack problem
• Nonlinear knapsack problem
• Inverse-parametric knapsack problem

The last three of these are discussed in Kellerer et al's reference work, Knapsack Problems.