Knapsack Problem Using Greedy Method

What is Knapsack Problem Using Greedy Method?

In this method, the Knapsack's filling is done so that the maximum capacity of the knapsack is utilized so that maximum profit can be earned from it. The knapsack problem using the Greedy Method is referred to as:
Given a list of n objects, say {I₁, I₂,……, I_n) and a knapsack (or bag).
The capacity of the knapsack is M.
Each object I_j has a weight w_j and a profit of p_j
If a fraction x_j (where x ∈ {0...., 1)) of an object I_j is placed into a knapsack, then a profit of p_jx_j is earned.
The problem (or Objective) is to fill the knapsack (up to its maximum capacity M), maximizing the total profit earned.
Mathematically:
Note that the value of x_j will be any value between 0 and 1 (inclusive). If any object I_j is completely placed into a knapsack, its value is 1 (x_j = 1). If we do not pick (or select) that object to fill into a knapsack, its value is 0 ( x_j = 0). Otherwise, if we take a fraction of any object, then its value will be any value between 0 and 1.

Knapsack Problem Algorithm Using Greedy Method

Knapsack Problem Using Greedy Method Pseudocode

A pseudo-code for solving knapsack problems using the greedy method is;
greedy fractional-knapsack (P[1...n], W[1...n], X[1..n]. M)
/*P[1...n] and W[1...n] contain the profit and weight of the n-objects ordered such that X[1...n] is a solution set and M is the capacity of knapsack*/
{

For j ← 1 to n do
X[j]← 0
profit ← 0 // Total profit of item filled in the knapsack
weight ← 0 // Total weight of items packed in knapsacks
j ← 1
While (Weight < M) // M is the knapsack capacity

{

if (weight + W[j] =< M)
X[j] = 1
weight = weight + W[j]
else{
X[j] = (M - weight)/w[j]
weight = M

}
Profit = profit + p[j] * X[j]
j++;
} // end of while
} // end of Algorithm

Knapsack Problem Using Greedy Method Example

We have thoroughly discussed the fractional knapsack problem and the algorithm for the knapsack problem using Greedy method. Now to understand it better, let us see an example.

Consider the knapsack instances, the capacity of the knapsack is 15, and 7 object has profit and weight as follows:

Which object is partially placed in the knapsack using the fractional knapsack problem?

1. X₄
2. X₂
3. X₁
4. X₃

Answer: Option B

Solution: Let us first find each object's profit by weight ratio.

Now we will arrange the profit by weight ratio in descending order and pick the objects accordingly.

The total capacity of the knapsack = 15

After selecting X₅ capacity = 15-1=14

After selecting X₁ capacity = 14-2=12

After selecting X₆ capacity = 12-4=8

After selecting X₇ capacity = 8-1=7

After selecting X₃ capacity = 7-5=2

After selecting X₂ capacity = 2-(2/3)*3=0

Thus we are taking only 2/3^rd weight of the object X₂

We take fractional parts from X_2.

Therefore, option B is correct.