# Knapsack Problem Using Greedy Method

By Priyanshu Vaish|Updated : September 29th, 2022

Knapsack Problem Using Greedy Method: The selection of some things, each with profit and weight values, to be packed into one or more knapsacks with capacity is the fundamental idea behind all families of knapsack problems. The knapsack problem had two versions that are as follows:

1. Fractional Knapsack Problem
2. 0 /1 Knapsack Problem

The fractional Knapsack problem using the Greedy Method is an efficient method to solve it, where you need to sort the items according to their ratio of value/weight. In a fractional knapsack, we can break items to maximize the knapsack's total value. This problem in which we can break an item is also called the Fractional knapsack problem. Here, we will see Knapsack Problem using Greedy method in detail, along with its algorithm and examples.

## 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 {I1, I2,……, In) and a knapsack (or bag).
The capacity of the knapsack is M.
Each object Ij has a weight wj and a profit of pj
If a fraction xj (where x ∈ {0...., 1)) of an object Ij is placed into a knapsack, then a profit of pjxj 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 xj will be any value between 0 and 1 (inclusive). If any object Ij is completely placed into a knapsack, its value is 1 (xj = 1). If we do not pick (or select) that object to fill into a knapsack, its value is 0 ( xj = 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 X1 X2 X3 X4 X5 X6 X7 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?

1. X4
2. X2
3. X1
4. X3

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

 object X1 X2 X3 X4 X5 X6 X7 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.

 X5 X1 X6 X7 X3 X2 6 5 4.5 3 3 1.6

The total capacity of the knapsack = 15

After selecting X5 capacity = 15-1=14

After selecting X1 capacity = 14-2=12

After selecting X6 capacity = 12-4=8

After selecting X7 capacity = 8-1=7

After selecting X3 capacity = 7-5=2

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

Thus we are taking only 2/3rd weight of the object X2

We take fractional parts from X2.

Therefore, option B is correct.

 Important GATE Topics Junction Field Effect Transistor Force Method Of Analysis Of Indeterminate Structure Mosfet Metal Oxide Silicon Field Effect Transistors Determinate And Indeterminate Structures Alloy Steel Astable Multivibrators Instrument Transformer Bistable Multivibrator Closed Loop Control System Truss And Frame

write a comment

## FAQs on Knapsack Problem Using Greedy Method

• The continuous knapsack problem is also known as the fractional knapsack problem. It is an algorithmic problem in combinatorial optimization in which the goal is to fill the knapsack (container) with fractional amounts of different materials chosen to maximize the value of the selected.

• The knapsack problems have various real-life applications, including financial modelling, production and inventory management systems, stratified sampling, design of queuing network models in manufacturing, and control of traffic overload in telecommunication systems.

• Sorting of n items (or objects) in decreasing order of the ratio Pj/Wj takes O (n log n) time. Since this is the lower bound for any comparison-based sorting algorithm. Therefore, the total time including sort is O(n log n).

• The basic idea of the greedy approach is to calculate the ratio value/weight for each item and sort the item based on this ratio. Then take the item with the highest ratio and add it to the knapsack until we can't add the following item as a whole, and at the end, add the following item as much as possible.

• The steps of the algorithm we shall use to solve our fractional knapsack problem using greedy method are:

1. Sort items by the ratio value/weight for each item, in descending order.
2. Start with the highest ratio item. Put items into the bag until the next item on the list cannot fit.
3. Try to fill any remaining capacity with the next item on the list that can fit.

### GATE & PSU CS

Computer ScienceGATEGATE CSENIELITOther ExamsQuick LinksMock Test GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com