A quadratic version of this problem, in which an additional value from off-diagonal elements of a matrix is introduced when two items are selected together, is a generalization of the problem of whether a graph has a clique of a given size.
A quadratic version of this problem, in which an additional value from off-diagonal elements of a matrix is introduced when two items are selected together, is a generalization of the problem of whether a graph has a clique of a given size. The one-dimensional stock cutting problem reduces to solving this problem, and most algorithms for solving it rely on initially ordering the variables by their profit-to-weight ratio. Allowing negative weights can reduce this problem to asking whether a nonempty subset of integers adds up to zero, and the general form of this problem can be solved in (*) pseudo-polynomial time using dynamic programming but is NP-complete overall. The 0-1 version of this problem is the most common formulation, in which an item of a given value and given weight can either be taken or left. For 10 points, identify this problem, which asks how to maximize the amount of profit when stuffing a subset of objects of varying weight into the namesake container.
A quadratic version of this problem, in which an additional value from off-diagonal elements of a matrix is introduced when two items are selected together, is a generalization of the problem of whether a graph has a clique of a given size.
knapsack problem