 In Progress
Lesson 26 of 43
In Progress

# Knapsack Problem

Fractions of items can be taken rather than having to make binary (0-1) choices for each item.

Fractional Knapsack Problem can be solvable by greedy strategy whereas 0 – 1 problem is not.

## Steps to solve the Fractional Problem:

1. Compute the value per pound  for each item.
2. Obeying a Greedy Strategy, we take as possible of the item with the highest value per pound.
3. If the supply of that element is exhausted and we can still carry more, we take as much as possible of the element with the next value per pound.
4. Sorting, the items by value per pound, the greedy algorithm run in O (n log n) time.
`Fractional Knapsack (Array v, Array w, int W)1. for i= 1 to size (v)2. do p [i] = v [i] / w [i]3. Sort-Descending (p)4. i ← 15. while (W>0)6. do amount = min (W, w [i])7. solution [i] = amount8. W= W-amount9. i ← i+110. return solution﻿`

Example: Consider 5 items along their respective weights and values: –

I = (I1,I2,I3,I4,I5)

w = (5, 10, 20, 30, 40)

v = (30, 20, 100, 90,160)

The capacity of knapsack W = 60

Now fill the knapsack according to the decreasing value of pi.

First, we choose the item Ii whose weight is 5.

Then choose item I3 whose weight is 20. Now,the total weight of knapsack is 20 + 5 = 25

Now the next item is I5, and its weight is 40, but we want only 35, so we chose the fractional part of it,

Solution:

Taking value per weight ratio i.e. pi=

Now, arrange the value of pi in decreasing order.