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.
YouTube Encyclopedic
-
1/3Views:25 847111 40635 313
-
Fractional Knapsack Problem | GeeksforGeeks
-
Greedy Algorithm | Fractional Knapsack Problem #01 - step by step guide
-
The Fractional Knapsack - Greedy Algorithms
Transcription
Problem definition
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 total value vi of that material. The goal is to choose an amount xi ≤ wi of each material, subject to the capacity constraint
Some formulations of this problem rescale the variables xi to be in the range from 0 to 1. In this case the capacity constraint becomes
Solution technique
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
- ^ 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.
- ^ a b c d Korte, Bernhard; Vygen, Jens (2012), "17.1 Fractional Knapsack and Weighted Median", Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics, vol. 21, Springer, pp. 459–461, ISBN 9783642244889.
- ^ Dantzig, George B. (1957), "Discrete-variable extremum problems", Operations Research, 5: 266–277, doi:10.1287/opre.5.2.266, MR 0089098.
This page was last edited on 4 January 2022, at 03:16