# Binary Knapsack Problem using Greedy Algorithm

Binary 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.”

Image Source: https://en.wikipedia.org/wiki/Knapsack_problem [link]

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
_{1}, x_{2}, x_{3}, . . . . . , x_{n}> is the set of n items. W = <w_{1}, w_{2}, w_{3}, . . . , w_{n}> and V = <v_{1}, v_{2}, v_{3}, . . . , 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} w_i x_i le M \]

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

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

## Algorithm

Algorithm to solve binary knapsack using greedy approach is described below:

**Algorithm **BINARY_KNAPSACK(W, V, M)
// W is an array of items
// V is an array of value or profit of items
// M is the capacity of the knapsack
// Items are pre sorted in decreasing order of pi = vi / wi ratio
S ← Φ // Variable to keep track of weight of selected items
i ← 1
P ← 0 // Variable to store earned profit
**while **S < M **do**
**if **(S + w[i]) ≤ M **then**
S ← Sunion ∪ w[i]
P ← P + v[i]
**else**
i ← i + 1
**end**
**end**

## Examples for Binary Knapsack

**Problem: Consider the following instance for the simple knapsack problem. Find the solution using the greedy method. **

N = 8

P = {11, 21, 31, 33, 43, 53, 55, 65}

W = {1, 11, 21, 23, 33, 43, 45, 55}

M = 110

**Solution:**

Let us arrange items by decreasing order of profit density. Assume that items are labeled as (I_{1}, I_{2}, I_{3}, I_{4}, I_{5}, I_{6}, I_{7}, I_{8}), have profit P = {11, 21, 31, 33, 43, 53, 55, 65} and weight W = {1, 11, 21, 23, 33, 43, 45, 55}.

Item | Weight | Value | p_{i} = v_{i} / w_{i} |

I_{1} | 1 | 11 | 11.0 |

I_{2} | 11 | 21 | 1.91 |

I_{3} | 21 | 31 | 1.48 |

I_{4} | 23 | 33 | 1.44 |

I_{5} | 33 | 43 | 1.30 |

I_{6} | 43 | 53 | 1.23 |

I_{7} | 45 | 55 | 1.22 |

I_{8} | 55 | 65 | 1.18 |

We shall select one by one item from the above table. We check the feasibility of item, if the inclusion of an item does not cross the knapsack capacity, then add it. Otherwise, skip the current item and process the next. We should stop when knapsack is full or all items are scanned

Initialize, Weight = 0, P = 0, knapsack capacity M = 110, Solution set S = { }.

**Iteration 1 :**

Weight = (Weight + w_{1}) = 0 + 1 = 1

Weight ≤ M, so select I_{1}

S = { I_{1} }, Weight = 1, P = 0 + 11 = 11

**Iteration 2 :**

Weight = (Weight + w_{2}) = 1 + 11 = 12

Weight ≤ M, so select I_{2}

S = { I_{1, }I_{2} }, Weight = 12, P = 11 + 21 = 32

**Iteration 3 :**

Weight = (Weight + w_{3}) = 12 + 21= 33

Weight ≤ M, so select I_{3}

S = { I_{1, }I_{2, }I_{3} }, Weight = 33, P = 32 + 31 = 63

**Iteration 4 :**

Weight = (Weight + w_{4}) = 33 + 23 = 56

Weight ≤ M, so select I_{4}

S = { I_{1, }I_{2, }I_{3, }I_{4} }, Weight = 56, P = 63 + 33 = 96

**Iteration 5 :**

Weight = (Weight + w_{5}) = 56 + 33 = 89

Weight ≤ M, so select I_{5}

S = { I_{1, }I_{2, }I_{3, }I_{4, }I_{5} }, Weight = 89, P = 96 + 43 = 139

**Iteration 6 :**

Weight = (Weight + w_{6}) = 89 + 43 = 132

Weight > M, so reject I_{6}

S = { I_{1, }I_{2, }I_{3, }I_{4, }I_{5} }, Weight = 89, P = 139

**Iteration 7 :**

Weight = (Weight + w_{7}) = 89 + 45= 134

Weight > W, so reject I_{7}

S = { I_{1, }I_{2, }I_{3, }I_{4, }I_{5} }, Weight = 89, P = 139

**Iteration 8 :** Weight = (Weight + w_{8}) = 89 + 55= 144

Weight > M, so reject I_{8}

S = { I_{1, }I_{2, }I_{3, }I_{4, }I_{5} }, Weight = 89, P = 139

All items are tested. The greedy algorithm selects items { I_{1, }I_{2, }I_{3, }I_{4, }I_{5} }, and gives a profit of 139 units

**Problem: Given the six items in the table below and a knapsack with weight limit 100, what is the solution to this knapsack problem?**

Item ID | Weight | Value | Value/Weight |

A | 100 | 40 | 0.4 |

B | 50 | 35 | 0.7 |

C | 40 | 20 | 0.5 |

D | 20 | 4 | 0.2 |

E | 10 | 10 | 1 |

F | 10 | 6 | 0.6 |

**Solution:**

Sort the items in decreasing order of value/weight ratio.

Item ID | Weight | Value | Value/Weight |

E | 10 | 10 | 1.0 |

B | 50 | 35 | 0.7 |

F | 10 | 6 | 0.6 |

C | 40 | 20 | 0.5 |

A | 100 | 40 | 0.4 |

D | 20 | 4 | 0.2 |

We shall select one by one item from the above table. We check the feasibility of item, if the inclusion of an item does not cross the knapsack capacity, we add it. Otherwise, we skip the current item and process the next. We should stop when knapsack is full or all items are scanned.

Initialize, Weight = 0, P = 0, knapsack capacity M = 100, Solution set S = { }.

**Iteration 1 : **

Weight = (Weight + W_{E}) = 0 + 10 = 10

Weight ≤ M, so select E

S = { E }, Weight = 10, P = 0 + 10 = 10

**Iteration 2 : **

Weight = (Weight + W_{B}) = 10 + 50 = 60

Weight ≤ M, so select B

S = { E, B }, Weight = 60, P = 10 + 35 = 45

**Iteration 3 :**

Weight = (Weight + W_{F}) = 60 + 10 = 70

Weight ≤ M, so select F

S = { E, B, F }, Weight = 70, P = 45 + 6 = 51

**Iteration 4 :**

Weight = (Weight + W_{C}) = 70 + 40 = 110

Weight > M, so reject item C

**Iteration 5 :**

Weight = (Weight + W_{A}) = 70 + 100 = 170

Weight > M, so reject item A

**Iteration 6 :**

Weight = (Weight + W_{D}) = 70 + 20 = 90

Weight ≤ M, so select D

S = { E, B, F, D }, Weight = 90, P = 51 + 4 = 55

All items are scanned. The greedy algorithm selects items { E, B, F, D }, and gives a profit of 55 units.

## 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 :