Knapsack problem using greedy method

An algorithm is a series of processes that execute calculations, data processing, and automated reasoning to solve a problem. A procedure that can be stated in a finite amount of time and space is referred to as an algorithm.

What is Knapsack problem?

The knapsack problem is a problem where a set of items is given along with weight and value of each item, and we must determine the number of each item to include in such a way that the total is equal to or less than the given capacity and the total value is as large as possible. Identifying the most restrictive restriction, ignoring the others, solving a knapsack problem, then adjusting the answer to satisfy the disregarded constraints is one basic approach to tough issues.

There are two versions of Knapsack problem:

· 0/1 Knapsack problem

· Fractional Knapsack problem

Here we will be discussing the fractional knapsack problem using an example.

In the Fractional Knapsack problem, the items are divisible, greedy method is used to solve this. If in any situation the knapsack is not including the complete item, we can add fraction of the item too.

Solving the Knapsack problem:

For the given set of items, the knapsack capacity is 60 kg.

Step1:

Calculate the value/ weight for each item.

v/w1 = 30/5

=6

v/w2 = 40/10

=4

v/w3 = 45/15

=3

v/w4 = 77/22

=3.5

v/w5 = 90/25

=3.6

Step2:

Arrange the items in descending order according to the value/weight ratio calculated.

Step3:

Start adding the items into the knapsack starting from the one with the highest ratio. Add as many items into the knapsack as possible.

Since we can add fractional values, therefore item 4 will be added as (20/22).

Total cost=160+(20/22) * 77

=160+70

=230 units

Pseudo Code for Knapsack problem

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W)

for i = 1 to n
do x[i] = 0
weight = 0
for i = 1 to n
if weight + w[i] ≤ W then
x[i] = 1
weight = weight + w[i]
else
x[i] = (W — weight) / w[i]
weight = W
break
return x

Time Complexity of Knapsack problem using greedy method is O(n*logn). The complexity of the entire task is O(n2) when employing a basic sort method (selection, bubble). If using quick sort or merge sort then the complexity of the whole problem is) O(n*logn).

This was all about Knapsack problem.

Thank you for reading!