[go: up one dir, main page]
Scribd
Upload
125 views14 pages

Unit - 3 Greedy Algorithm (Fractional Knapsack Problem)

The document discusses the Fractional Knapsack Problem, where the goal is to maximize profit by selecting objects with given weights and profits while adhering to a weight limit. It explains the greedy algorithm approach, allowing for the selection of fractions of objects, and provides two examples illustrating the selection process and calculations for total profit. The algorithm sorts objects based on their profit-to-weight ratio and selects them accordingly until the knapsack's capacity is reached.

Uploaded by

Yashvant Solanki
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
125 views14 pages

Unit - 3 Greedy Algorithm (Fractional Knapsack Problem)

The document discusses the Fractional Knapsack Problem, where the goal is to maximize profit by selecting objects with given weights and profits while adhering to a weight limit. It explains the greedy algorithm approach, allowing for the selection of fractions of objects, and provides two examples illustrating the selection process and calculations for total profit. The algorithm sorts objects based on their profit-to-weight ratio and selects them accordingly until the knapsack's capacity is reached.

Uploaded by

Yashvant Solanki
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 14

GREEDY

ALGORITHM
FRACTIONAL
KNAPSACK PROBLEM
• We are giving n objects and a knapsack.

• Object i has positive weight wi and profit pi


(for I = 1,2,3……n)

• The knapsack can carry at most weight W.

• Our aim is to fill the knapsack in such a way


that “maximize profit” of include objects
while satisfying the capacity constraints.
CONTINUE

• In fractional knapsack problem, we assume


that the objects can be broken into smaller
pieces, so we may decide to carry only a
fraction xi of object i.
• Where 0<= xi <= 1
• In this case, object i contribute xi * wi to the
total weight in the knapsack and xi * pi to
the total profit.
• Symbolic representation of the problem can
be given as follows:
CONTINUE
EXAMPLE – 1
Solve following knapsack problem using
greedy algorithm. Capacity of knapsack W =
100. Given wi and pi is as follows:

Object i wi pi
1 10 20
2 20 30
3 30 66
4 40 40
5 50 60
CONTINUE
Object i wi pi pi / wi
1 10 20 2
2 20 30 1.5
3 30 66 2.2
4 40 40 1
5 50 60 1.2

Sort pi / wi in descending order for choose object


Object i wi pi pi / wi
3 30 66 2.2
1 10 20 2
2 20 30 1.5
5 50 60 1.2
4 40 40 1
CONTINUE
1. Choose the item with the highest pi / wi as we
want total weight W = 100 in knapsack
So choose item 3 weight = 30
choose item 1 weight = 40 (total weight =
30+10)
choose item 2 weight = 60 (total weight =
30+10+20)
choose item 5 weight = 110
(total weight = 30+10+20+50)
(we can not take whole object)

But capacity of knapsack in W = 100 so, we can add only a


fraction of item 5

Find Fraction: W - wi / x [weight]

Max Current Choose


weight of weight items
knapsack of weight
knapsac
k
So, 100-60 / 50 = 0.8 (part of item 5 will be
added)
CONTINUE

• Solution set x = {1, 1, 1, 0, 0.8}

Note: In which 1 means whole objects


selected, 0 means no object selected and 0.8
means fraction of specific object.

Total Profit = 20 + 30 + 66 + (0.8 *60) = 164


EXAMPLE – 2
Solve following knapsack problem using greedy
algorithm. W = 15 and n = 7
(p1, p2, …p7) = (10, 5, 15, 7, 6, 18, 3)
(w1, w2, ….w7) = (2, 3, 5, 7, 1, 4, 1)

Object i wi pi
1 2 10
2 3 5
3 5 15
4 7 7
5 1 6
6 4 18
7 1 3
CONTINUE

Object i Wi Pi Pi / wi
1 2 10 5
2 3 5 1.67
3 5 15 3
4 7 7 1
5 1 6 6
6 4 18 4.5
7 1 3 3

Sort pi / wi in descending order for choose object


CONTINUE

Object i Wi Pi Pi / wi
5 1 6 6
1 2 10 5
6 4 18 4.5
3 5 15 3
7 1 3 3
2 3 5 1.67
4 7 7 1
CONTINUE
1. Choose the item with the highest pi / wi as we
want total weight W = 15 in knapsack
So choose item 5 weight = 1
choose item 1 weight = 3 (total weight = 1+2)
choose item 6 weight = 7 (total weight = 3+4)
choose item 3 weight = 12 (total weight = 7+5)
choose item 7 weight = 13 (total weight = 12+1)
choose item 2 weight = 16 (total weight = 13+3)
(we can not take whole object because W = 15)

But capacity of knapsack in W = 15 so, we can add only a


fraction of item 2

Find Fraction: W - wi / x [weight]

Max Current Choose


weight of weight items
knapsack of weight
knapsac
k
So, 15-13 / 3 = 0.67 (part of item 2 will be
added)
CONTINUE

• Solution set x = {1, 0.67, 1, 0, 1, 1, 1}

Note: In which 1 means whole objects


selected, 0 means no object selected and 0.67
means fraction of specific object.

Total Profit = 10 + (0.67*5) + 15 + 6 + 18 + 3


= 55.35
ALGORITHM FOR FRACTIONAL
KNAPSACK PROBLEM

You might also like