Continuous knapsack problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In theoretical computer science, the continuous knapsack problem (also known as the fractional knapsack problem) is an algorithmic problem in combinatorial optimization in which the goal is to fill a container (the "knapsack") with fractional amounts of different materials chosen to maximize the value of the selected materials.[1][2] It resembles the classic knapsack problem, in which the items to be placed in the container are indivisible; however, the continuous knapsack problem may be solved in polynomial time whereas the classic knapsack problem is NP-hard.[1] It is a classic example of how a seemingly small change in the formulation of a problem can have a large impact on its computational complexity.

Problem definition[edit]

An instance of either the continuous or classic knapsack problems may be specified by the numerical capacity W of the knapsack, together with a collection of materials, each of which has two numbers associated with it: the weight wi of material that is available to be selected and the value per unit weight vi of that material. The goal is to choose an amount xi ≤ wi of each material, subject to the capacity constraint

\sum_i x_i\le W

and maximizing the total benefit

\sum_i x_i v_i.

In the classic knapsack problem, each of the amounts xi must be either zero or wi; the continuous knapsack problem differs by allowing xi to range continuously from zero to wi.[1] Some formulations of this problem rescale the variables xi to be in the range from 0 to 1

Solution technique[edit]

The continuous knapsack problem may be solved by a greedy algorithm, first published in 1957 by George Dantzig,[2][3] that considers the materials in sorted order by their values per unit weight. For each material, the amount xi is chosen to be as large as possible:

  • If the sum of the choices made so far equals the capacity W, then the algorithm sets xi = 0.
  • If the difference d between the sum of the choices made so far and W is smaller than wi, then the algorithm sets xi = d.
  • In the remaining case, the algorithm chooses xi = wi.

Because of the need to sort the materials, this algorithm takes time O(n log n) on inputs with n materials.[1][2] However, by adapting an algorithm for finding weighted medians, it is possible to solve the problem in time O(n).[2]

References[edit]

  1. ^ a b c d Goodrich, Michael T.; Tamassia, Roberto (2002), "5.1.1 The Fractional Knapsack Problem", Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, pp. 259–260 .
  2. ^ a b c d Korte, Bernhard; Vygen, Jens (2012), "17.1 Fractional Knapsack and Weighted Median", Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics 21, Springer, pp. 459–461, ISBN 9783642244889 .
  3. ^ Dantzig, George B. (1957), "Discrete-variable extremum problems", Operations Research 5: 266–277, doi:10.1287/opre.5.2.266, MR 0089098 .