Fraction Knapsack

Created

Dec 7, 2025

Last Modified

3 months ago

Fractional Knapsack

In the fractional knapsack problem, we have eight items of known values and weights. The capacity of the knapsack is also given. The objective is to fill the knapsack with these items in order to maximise the profit, but the total weight of the chosen objects cannot be more than the capacity of the knapsack. 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_{i}, \dots, w_{n}$

Values = $v_{1}, v_{2}, \dots, v_{i}, \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}

w h er e 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)

powershell

for p = 1 to n do :
    x[i] = 0.0;

u = m; # avaialble 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 simply $O (n)$ because of a simple for-loop with a maximum of n iterations. So the algorithm takes linear time to solve the fractional knapsack.

Solve the Given Fractional Knapsack Problem

Capacity of knapsack = 7

Items Data

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

1. Initialization

powershell

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 the table 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 = 5 > u$ .
Take fraction $x_{2} = u/5 = 1/5 = 0.2$ .
Weight added $= 5 \times 0.2 = 1$
Profit $= 30 \times 0.2 = 6$ .
Item 1:
no capacity left $x_{3} = 0$ .

5. Calculate the Total

x = [1, 0.2, 0]

v = [60, 30, 20]

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

60 + 6 + 0 = 0