Continuous knapsack problem

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 w_i of material that is available to be selected and the total value v_i of that material. The goal is to choose an amount x_i ≤ w_i of each material, subject to the capacity constraint $${\displaystyle \sum _{i}x_{i}\leq W}$$ and maximizing the total benefit $${\displaystyle \sum _{i}x_{i}v_{i}.}$$ In the classic knapsack problem, each of the amounts x_i must be either zero or w_i; the continuous knapsack problem differs by allowing x_i to range continuously from zero to w_i.^[1]

Some formulations of this problem rescale the variables x_i to be in the range from 0 to 1. In this case the capacity constraint becomes $${\displaystyle \sum _{i}x_{i}w_{i}\leq W,}$$ and the goal is to maximize the total benefit $${\displaystyle \sum _{i}x_{i}v_{i}.}$$

Summarize Timeline Fact Check

The continuous knapsack problem admits a greedy solution first published in 1957 by George Dantzig.^[3][4] Each material is assigned the ratio ${\displaystyle 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 ${\displaystyle (10,20,20,10)}$, values ${\displaystyle (50,80,60,20)}$, and that the capacity of the knapsack is ${\displaystyle W=34}$. The value-to-weight ratio of each item is computed, giving ${\displaystyle (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 ${\displaystyle 0.2}$ of item 3.

If comparison-based sorting is used, this algorithm runs in ${\displaystyle O(n\log n)}$ with respect to ${\displaystyle n}$ materials.^[1][2] However, by adapting an algorithm for finding weighted medians, it is possible to solve the problem in time ${\displaystyle O(n)}$.^[2]

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 ${\displaystyle (1,1,0.2,0)}$ of 4 items (sorted by the value-to-weight ratio) and the new solution takes fractions ${\displaystyle (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.