Fraction Knapsack

Dec 7, 2025

Updated 1 day ago

2 min read

Fractional Knapsack Problem: Greedy Algorithm with Solved Example

In the fractional knapsack problem, we have items of known values and weights, and a knapsack of given capacity. The objective is to fill the knapsack to maximise the profit, but the total weight of the chosen objects cannot exceed the capacity. Unlike the 0/1 knapsack problem, we can break weights into fractional values between zero and one, so fractional values are allowed.

We have:

Items = $N$ , Weights = $w_{1}, w_{2}, \dots, w_{n}$ , Values = $v_{1}, v_{2}, \dots, v_{n}$

If a fraction of the i-th item is selected, then:

Profit Earned

profit earned = v_{i} \cdot x_{i}

Weight Added to the Knapsack

w_{i} \cdot x_{i}, 1 \leq i \leq n

Thus the total profit earned is:

Z = v_{1} x_{1} + v_{2} x_{2} + \dots + v_{i} x_{i} + \dots + v_{n} x_{n}

And the total weight of chosen objects should satisfy:

w_{1} x_{1} + w_{2} x_{2} + \dots + w_{i} x_{i} + \dots + w_{n} x_{n} \leq M

Mathematical Formulation

Maximize:

Z = i = 1 \sum n v_{i} x_{i}

Subject to:

i = 1 \sum n w_{i} x_{i} \leq M, 0 \leq x_{i} \leq 1 \forall i

$∴$ the unknown is $x_{i}$ , which is the solution we want to determine.

Greedy Idea (Optimal)

The greedy strategy is to always select the item with the highest value-to-weight ratio ( $v_{i} / w_{i}$ ) first. This approach is provably optimal for the fractional knapsack — see Greedy Approach for Algorithm Design.

bash

for p = 1 to n do :
    x[i] = 0.0;
u = m; # available capacity
for i = 1 to n do :
{
    if (w[i] > u) then break;
    x[i] = 1.0;
    u = u - w[i];
}
if (i <= n) :
    x[i] = u / w[i];

Time Complexity

The complexity of this algorithm is $O (n lo g n)$ — sorting the items by $v_{i} / w_{i}$ takes $O (n lo g n)$ , and the greedy selection loop runs in $O (n)$ . So the sorting step dominates. For more on asymptotic complexity, see Asymptotic Notation.

Solved Example: Fractional Knapsack Problem

Capacity of knapsack = 7

Items Data

Item	Weight	Value
1	4	20
2	5	30
3	6	60

1. Initialization

bash

i = 1 to 3 do :
    x[i] = 0.0
# x = [0, 0, 0]

2. Finding $v_{i} / w_{i}$ for All Items

Item (i)	Weight $w_{i}$ )	Value $v_{i}$ )	$v_{i} / w_{i}$
1	4	20	5
2	5	30	6
3	6	60	10

3. Arrange in Decreasing Order of $v_{i} / w_{i}$

i.e., $v_{i} / w_{i} \geq v_{i + 1} / w_{i + 1}$

Item (i)	Weight $w_{i}$ )	Value $v_{i}$ )	$v_{i} / w_{i}$
1	6	60	10
2	5	30	6
3	4	20	5

4. Greedy Selection

Take Item 1 fully: Weight added = 6. Remaining capacity $u = 7 - 6 = 1$ . Profit = 60. $x_{1} = 1$
Next, Item 2 weight = 5 > $u$ = 1. Take fraction $x_{2} = u /5 = 1/5 = 0.2$ . Weight added = $5 \times 0.2 = 1$ . Profit = $30 \times 0.2 = 6$ .
Item 3: No capacity left. $x_{3} = 0$ .

5. Total Profit

x = [1, 0.2, 0], v = [60, 30, 20]

60 \times 1 + 30 \times 0.2 + 20 \times 0

60 + 6 + 0 = 66

Related Notes: