Continuous knapsack problem

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 (with a fixed capacity) fractional amounts of different materials chosen to maximize the value of the selected materials. It is a variation of 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. 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.

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 (with a fixed capacity) fractional amounts of different materials chosen to maximize the value of the selected materials. It is a variation of 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. 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== An instance of either the continuous or classic knapsack problems may be specified by the numerical capacity of the knapsack, together with a collection of materials, each of which has two numbers associated with it: the weight of material that is available to be selected and the total value of that material. The goal is to choose an amount of each material, subject to the capacity constraint \sum_i x_i \le W and maximizing the total benefit \sum_i \left(\frac{x_i}{w_i}\right) v_i. In the classic knapsack problem, each of the amounts must be either zero or ; the continuous knapsack problem differs by allowing to range continuously from zero to . Some formulations of this problem rescale the variables to be in the range from 0 to 1. In this case the capacity constraint becomes \sum_i x_i w_i \leq W, and the goal is to maximize the total benefit \sum_i x_i v_i. ==Algorithm== The continuous knapsack problem admits a greedy solution first published in 1957¹ by George Dantzig. Each material is assigned the ratio v_i/w_i , and then the materials are sorted in descending order of this ratio. While the total weight of materials chosen is less than W, the algorithm takes the largest possible fraction of the first item in the sorted list. For example, suppose we have 4 items with weights (10, 20, 20, 10) , values (50, 80, 60, 20) , and that the capacity of the knapsack is W = 34 . The value-to-weight ratio of each item is computed, giving (5, 4, 3, 2) . In this case the items are already sorted in descending order of ratio. The algorithm then takes all of item 1, all of item 2, and 0.2 of item 3. If comparison-based sorting is used, this algorithm runs in O(n \log n) with respect to n materials. However, by adapting an algorithm for finding weighted medians, it is possible to solve the problem in time O(n) . The proof of correctness follows by a standard exchange argument. Suppose that we have a solution which is not the greedy solution. Take the first instance where the new solution and the greedy solution differ. For example, if the greedy solution takes fractions (1, 1, 0.2, 0) of 4 items (sorted by the value-to-weight ratio) and the new solution takes fractions (1, 1, 0, 0.4) of the same 4 items, then they differ in the third entry. In general, the greedy solution takes weights of items sorted by ratio, so the greedy solution has assigned more weight to a higher-ratio item. Since both solutions assign the same total weights across items, the new solution is forced to assign weight to items of a lower ratio. So the new assignment has a value no greater than the value given by the greedy assignment. An exact procedure that solves the log-linear continuous knapsack problem in polynomial time was found in 2024. It is easily verified from the procedure that for such a problem with rational numerical values for its parameters, the solution has rational numerical values. ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375874861 under CC BY-SA 4.0; modifications have been made.