## Knapsack Problem-

You are given a knapsack (a kind of shoulder bag) with a limited weight capacity and few items each having some weight and value.

The problem states-

“Which items should be placed in the knapsack so that the value or profit that is obtained by putting the items in the knapsack is maximum and the weight limit of the knapsack also does not exceed?” ## Knapsack Problem Variants-

Knapsack problem has the following two variants-

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

## Fractional Knapsack Problem-

In Fractional Knapsack Problem,

• As the name suggests, items are divisible here.
• We can even put the fraction of any item in the knapsack if taking the complete item is not possible.
• It is solved using Greedy Approach.

## Steps for solving Fractional Knapsack Problem using Greedy Approach-

### Step-01:

For each item, compute its value / weight ratio.

### Step-02:

Arrange all the items in the decreasing order of their value / weight ratios.

### Step-03:

Start putting the items in the Knapsack beginning from the item with the highest ratio. Put as many items as you can in the Knapsack.

## Time Complexity-

While solving the problem,

• The main time taking step is the sorting of all items in the decreasing order of their value / weight ratios.
• If the items are already arranged in the required order, the while loop takes O(n) time.
• Quick sort’s average time complexity is O(nlogn), therefore total time taken including the sort is O(nlogn).

## Problem-

For the given set of items and knapsack capacity = 60 kg, find the optimal solution for the fractional knapsack problem making use of greedy approach.

 Item Weight Value 1 5 30 2 10 40 3 15 45 4 22 77 5 25 90

OR

Find the optimal solution for the fractional knapsack problem making use of greedy approach. Consider-

n = 5

w = 60 kg

(w1, w2, w3, w4, w5) = (5, 10, 15, 22, 25)

(b1, b2, b3, b4, b5) = (30, 40, 45, 77, 90)

OR

A thief enters a house for robbing it. He can carry a maximal weight of 60 kg into his bag. There are 5 items in the house with the following weights and values. What items should thief take if he can even take the fraction of any item with him?

 Item Weight Value 1 5 30 2 10 40 3 15 45 4 22 77 5 25 90

## Solution-

### Step-01:

Compute the value / weight ratio for each item-

 Items Weight Value Ratio 1 5 30 6 2 10 40 4 3 15 45 3 4 22 77 3.5 5 25 90 3.6

### Step-02:

Sort all the items in the decreasing order of their value / weight ratios-

I1          I2          I5          I4          I3

(6)       (4)        (3.6)      (3.5)       (3)

### Step-03:

Start filling the knapsack by putting the items in it one by one.

 Knapsack Weight Items in the Knapsack Cost 60 Ø 0 55 I1 30 45 I1, I2 70 20 I1, I2, I5 160

Now,

• Knapsack weight left to be filled is 20 kg but item-4 has a weight of 22 kg.
• Had the problem been a 0/1 knapsack problem, we would have stopped and reported that the knapsack has items < I1 , I2 , I5 > and the knapsack’s total cost is 160.
• But because in fractional knapsack problem we can even take the fraction of any item.
• So, our knapsack will contain the items-

< I1 , I2 , I5 , (20/22) I4 >

Now,

Total cost of the knapsack

= 160 + (20/27) x 77

= 160 + 70

= 230 units

To gain better understanding about Fractional Knapsack Problem,

Watch this Video lecture

## Download the handwritten notes of “Fractional Knapsack Problem Using Greedy Approach” here- Get more notes and other study material of Design and Analysis of Algorithms (DAA).

Watch video lectures by visiting our YouTube channel LearnVidFun.