Fractional Knapsack Using Greedy Algorithm

Fractional Knapsack problem is defined as, “Given a set of items having some weight and value/profit associated with it. The knapsack problem is to find the set of items such that the total weight is less than or equal to a given limit (size of knapsack) and the total value/profit earned is as large as possible.”

Knapsack problem has two variants.

• Binary or 0/1 knapsack : Item cannot be broken down into parts.
• Fractional knapsack : Item can be divided into parts.

Given a set of items, each having some weight and value/profit associated with it. The goal is to find the set of items such that the total weight is less than or equal to a given limit (size of knapsack) and the total value/profit earned is as large as possible.

• The knapsack is an optimization problem and it is useful in solving resource allocation problem.
• Let X = <x₁, x₂, x₃, . . . . . , x_n> is the set of n items. W = <w₁, w₂, w₃, . . . , w_n> and V = <v₁, v₂, v₃, . . . , v_n> are the set of weight and value associated with each items in x, respectively. Knapsack capacity is M.
• Select items one by one from the set of items x and fill the knapsack such that it would maximize the value. Knapsack problem has two variants. 0/1 knapsack does not allow breaking of items. Either add entire item in a knapsack or reject it. It is also known as a binary knapsack. Fractional knapsack allows the breaking of items. So profit will also be considered accordingly.

• Knapsack problem can be formulated as follow :

Maximize \[ sum_{i=1}^{n} v_i x_i \] subjected to  \[ sum_{i=1}^{n} v_i x_i le M \]

\[ x_i in (0, 1) \] for binary knapsack

\[ x_i in [0, 1] \] for fractional knapsack

Algorithm

Algorithm GREEDY_FRACTIONAL_KNAPSACK(X, V, W, M)
// Description : Solve the knapsack problem using greedy approach

// Input: 
X: An array of n items
V: An array of profit associated with each item
W: An array of weight associated with each item
M: Capacity of knapsack

// Output : 	
SW: Weight of selected items
SP: Profit of selected items
// Items are presorted in decreasing order of pi = vi / wi ratio

S ← Φ	  // Set of selected items, initially empty
SW ← 0    // weight of selected items
SP ← 0    // profit of selected items
i ← 1

while i ≤ n do
    if (SW + w[i]) ≤ M then
        S ← S ∪ X[i]                
        SW ← SW + W[i]
        SP ← SP + V[i]
    else
        frac ← (M - SW) / W[i]		
        S ← S ∪ X[i] * frac	     // Add fraction of item X[i]
        SP ← SP + V[i] * frac    // Add fraction of profit
        SW ← SW + W[i] * frac    // Add fraction of weight
    end
    i ← i + 1
end

Complexity Analysis

• For one item there are two choices, either to select or reject. For 2 items we have four choices:
  • Select both items
  • Reject both items
  • Select first and reject second
  • Reject first and select second
• In general, for n items, knapsack has 2ⁿ choices. So brute force approach runs in O(2ⁿ) time.
• We can improve performance by sorting items in advance. Using merge sort or heap sort, n items can be sorted in O(nlog₂n) time. Merge sort and heap sort are non-adaptive and their running time is the same in best, average and worst case.
• To select the items, we need one scan to this sorted list, which will take O(n) time.
• So the total time required is
  T(n) = O(nlog₂n) + O(n) = O(nlog₂n).

Examples of Fractional Knapsack

Problem: Consider the following instances of the fractional knapsack problem: n = 3, M = 20, V = (24, 25, 15) and W = (18, 15, 20) find the feasible solutions.

Solution:

Let us arrange items by decreasing order of profit density. Assume that items are labeled as X = (I₁, I₂, I₃), have profit V = {24, 25, 15} and weight W = {18, 15, 20}.

Item (xi)	Value (vi)	Weight (wi)	pi = vi / wi
I2	25	15	1.67
I1	24	18	1.33
I3	15	20	0.75

We shall select one by one item from Table. If the inclusion of an item does not cross the knapsack capacity, then add it. Otherwise, break the current item and select only the portion of item equivalent to remaining knapsack capacity. Select the profit accordingly. We should stop when knapsack is full or all items are scanned.

Initialize, Weight of selected items, SW = 0,

Profit of selected items, SP = 0,

Set of selected items, S = { },

Here, Knapsack capacity M = 20.

Iteration 1 : SW= (SW + w₂) = 0 + 15 = 15

SW ≤ M, so select I₂

S = { I₂ }, SW = 15, SP = 0 + 25 = 25

Iteration 2 : SW + w₁ > M, so break down item I_1.

The remaining capacity of the knapsack is 5 unit, so select only 5 units of item I₁.

frac = (M – SW) / W[i] = (20 – 15) / 18 = 5 / 18

S = { I_2, I₁ * 5/18 }

SP = SP + v₁ * frac = 25 + (24 * (5/18)) = 25 + 6.67 = 31.67

SW = SW + w₁ * frac = 15 + (18 * (5/18)) = 15 + 5 = 20

The knapsack is full. Fractional Greedy algorithm selects items { I_2, I₁ * 5/18 }, and it gives a profit of 31.67 units.

Problem: Find the optimal solution for knapsack problem (fraction) where knapsack capacity = 28, P = {9, 5, 2, 7, 6, 16, 3} and w = {2, 5, 6, 11, 1, 9, 1}.

Solution:

Arrange items in decreasing order of profit to weight ratio

Item	Profit pi	Weight wi	Ratio vi/wi
I5	6	1	6.00
I1	9	2	4.50
I7	3	1	3.00
I6	16	9	1.78
I2	5	5	1.00
I4	7	11	0.64
I3	2	6	0.33

Initialize, Weight = 0, P = 0, M = 28, S = { }

Where S is the solution set, P and W is profit and weight of included items, respectively. M is the capacity of the knapsack.

Iteration 1

(Weight + w₅) ≤ M, so select I₅

So, S = { I₅ }, Weight = 0 + 1 = 1, P = 0 + 6= 6

Iteration 2

(Weight + w₁) ≤ M, so select I₁

So, S = {I₅ ,I₁ }, Weight = 1 + 2 = 3, P = 6 + 9= 15

Iteration 3

(Weight + w₇) ≤ M, so select I₇

So, S = {I₅, I₁, I₇ }, Weight = 3 + 1 = 4, P = 15 + 3= 18

Iteration 4

(Weight + w₆) ≤ M, so select I₆

So, S = {I₅, I₁, I₇, I₆ }, Weight = 4 + 9 = 13, P = 18 + 16= 34

Iteration 5

(Weight + w₂) ≤ M, so select I₂

So, S = {I₅, I₁, I₇, I₆, I₂ }, Weight = 13 + 5 = 18, P = 34 + 5= 39

Iteration 6

(Weight + w₄) > M, So I₄ must be broken down into two parts x and y such that x = capacity left in knapsack and y = I₄ – x.

Available knapsack capacity is 10 units. So we can select only (28 – 18) / 11 = 0.91 unit of I₄.

So S = {I₅, I₁, I₇, I₆, I₂, 0.91 * I₄ }, Weight = 18 + 0.91*11 = 28, P = 39 + 0.91 * 7= 45.37

Some Popular Problems Solved by Greddy Algorithm

Greedy algorithms are used to find an optimal or near-optimal solution to many real-life problems. A few of them are listed below :

• Binary Knapsack Problem
• Fractional Knapsack Problem
• Job Scheduling Problem
• Activity Selection Problem
• Huffman Coding
• Optimal Storage on Tapes
• Optimal Merge Pattern
• Prim’s Algorithm
• Kruskal’s Algorithm
• Dijkstra’s Algorithm

---

Additional Reading: Read article