Question

KNAPSACK Optimization Problem using Greedy Method
Problem 1:
Item Weight Value
1 14 20
2 6 16
3 10 8
4 5 10
5 4 12
Allowed weight = 24 Kg

Problem 2:
Item Weight Value
1 6 30
2 8 40
3 15 45
4 22 88
5 25 80
Allowed weight = 60 Kg

Problem 3:
Item Weight Value
1 6 30
2 8 40
3 15 45
4 22 88
5 25 80
Allowed weight = 60 Kg

Answer 1

by using fractional method to solve the knapsack problrm using greedy approach:

Problem 1:
Item Weight Value Value /weight
1 14 20 20/14
2 6 16 16/6
3 10 8 8/10
4 5 10 10/5
5 4 12 12/4
Allowed weight = 24 Kg

greedy to weight ,

W=24-4=20,V5=12

W=20-5=15,V4=10

W=15-6=9,V2=16

W=9-9=0

V3=(9/10)*8=7.2

Value=12+10+16+7.2=45.2

items chosen=(0,1,9/10,1,1)

greedy to value,

Item Weight Value Value /weight
1 14 20 20/14
2 6 16 16/6
3 10 8 8/10
4 5 10 10/5
5 4 12 12/4
Allowed weight = 24 Kg

W=24-14=10,V1=20

W=10-6=4,V2=16

W=4-4=0,V5=12

Value=20+16+12=48

items chosen=(1,1,0,0,1)

greedy to value/weight

Item Weight Value Value /weight
1 14 20 20/14=1.42
2 6 16 16/6=2.66
3 10 8 8/10=0.8
4 5 10 10/5=2
5 4 12 12/4=3

Allowed weight = 24 Kg

W=24-4=20,V5=12

W=20-6=14,V2=16

W=14-5=9,V4=10

W=9-9=0,V1=(9/14)*20=12.8

Value=12+16+10+12.85=50.8

items chosen=(9/14,1,0,1,1)

Problem 2:
Item Weight Value
1 6 30
2 8 40
3 15 45
4 22 88
5 25 80
Allowed weight = 60 Kg

greedy to weight ,

w=60-6=54,V1=30

w=54-8=46,V2=40

w=46-15=31,V3=45

w=31-22=9,V4=88

w=9-9=0,V5=9/25*80=28.8

Value=30+40+45+88+28.8=231.8

items chosen=(1,1,1,1,9/25)

greedy to value,

Item Weight Value
1 6 30
2 8 40
3 15 45
4 22 88
5 25 80
Allowed weight = 60 Kg

W=60-22=38,V4=88

W=38-25=13,V5=80

W=13-13=0,V3=13/15*45=39

Value=88+80+39=207

items chosen=(0,0,13/15,1,1)

greedy to value/weight,

Item Weight Value Value/Weight
1 6 30 30/6=5
2 8 40 40/8=5
3 15 45 45/15=3
4 22 88 88/22=4
5 25 80 80/25=3.2
Allowed weight = 60 Kg

W=60-6=54,V1=30

W=54-8=46,V2=40

W=46-22=24,V4=88

W=24-24=0,V5=24/25*80=76.8

Value=30+40+88+76.8=234.8

items chosen=(1,1,0,1,24/25)