Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Quadratic knapsack problem
open-in-new
<p>The quadratic knapsack problem (QKP), first introduced in 19th century, is an extension of <a href="/facts/Knapsack_problem/HMIdVJH5">knapsack problem</a> that allows for quadratic terms in the <a href="/facts/Objective_function/xv5ozuhl">objective function</a>: Given a set of items, each with a weight, a value, and an extra profit that can be earned if two items are selected, determine the number of items to include in a collection without exceeding capacity of the <a href="/facts/Knapsack/uvI4lVWl">knapsack</a>, so as to maximize the overall profit. Usually, quadratic knapsack problems come with a restriction on the number of copies of each kind of item: either 0, or 1. This special type of QKP forms the 0-1 quadratic knapsack problem, which was first discussed by Gallo et al. The 0-1 quadratic knapsack problem is a variation of the knapsack problem, combining the features of the 0-1 knapsack problem and the quadratic knapsack problem. </p>