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_{1}, I_{2},……, 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_{j}x_{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:
Object | X_{1} | X_{2} | X_{3} | X_{4} | X_{5} | X_{6} | X_{7} |
Weight | 2 | 3 | 5 | 7 | 1 | 4 | 1 |
Profit | 10 | 5 | 15 | 7 | 6 | 18 | 3 |
Which object is partially placed in the knapsack using the fractional knapsack problem?
- X_{4}
- X_{2}
- X_{1}
- X_{3}
Answer: Option B
Solution: Let us first find each object's profit by weight ratio.
object | X_{1} | X_{2} | X_{3} | X_{4} | X_{5} | X_{6} | X_{7} |
Profit/weight | 5 | 1.66 | 3 | 1 | 6 | 4.5 | 3 |
Now we will arrange the profit by weight ratio in descending order and pick the objects accordingly.
X_{5} | X_{1} | X_{6} | X_{7} | X_{3} | X_{2} |
6 | 5 | 4.5 | 3 | 3 | 1.6 |
The total capacity of the knapsack = 15
After selecting X_{5} capacity = 15-1=14
After selecting X_{1} capacity = 14-2=12
After selecting X_{6} capacity = 12-4=8
After selecting X_{7} capacity = 8-1=7
After selecting X_{3} capacity = 7-5=2
After selecting X_{2} capacity = 2-(2/3)*3=0
Thus we are taking only 2/3^{rd} weight of the object X_{2}
We take fractional parts from X_{2.}
Therefore, option B is correct.
Comments
write a comment