Question

please I would like assistance with this which are question 1 and 2, thank you

2. We have 5 objects, and the weights and values are No. 2 3 4 5 10 20 30 50 V 20 30 66 60 55 W 40 The knapsack can carry a weight not exceeding 90, find a subset items and give the total weight and value for following algorithms: 1) By using the algorithm of greedy of value for 0-1 knapsack problem? By selecting the highest value first. 2) By using the algorithm of greedy of weight for 0-1 knapsack problem? By selecting lightest item first. 3) By using the algorithm of greedy of density for 0-1 knapsack problem? By selecting the highest density item first. 4) By using the algorithm of greedy of density for fractional knapsack problem? By selecting the highest density item first.

Answer 1

Solution:

(2)

Given,

=>Number of objects = 5

No	1	2	3	4	5
w	10	20	30	40	50
v	20	30	66	60	55

=>Knapsack capacity = 90

(1)

Explanation:

=>Using greedy algorithm for 0-1 knapsack with highest value selection first.

=>Value order: 66 > 60 > 55 > 30 > 20

=>Highest value = 66 with weight = 30 is selected first and put it into the knapsack so capacity remaining = 60. Inserted object = 3

=>Now second heighest value = 60 with weight = 40 so put it into the knapsack so capacity remaining = 20. Inserted object = 4

=>Now value = 55 will be selected with weight 50 but as knapsack remaining capacity is 20( 50 > 20) so this weight is not possible to put into knapsack using 0-1 kanpsack(without breaking the weight).

=>Now value = 30 with weight = 20 will be selected so put it into knapsack so remaining capacity = 0 and we will stop here. Inserted object = 2

=>Hence subset of items = {2, 3, 4}

=>Total weight = 90

=>Total value = 66 + 60 + 30

=>Total value = 156

(2)

Explanation:

=>Using greedy algorithm for 0-1 knapsack by selecting lighest item first.

=>Order of weight: 10 < 20 < 30 < 40 < 50

=>Object 1 with weight 10 and value 20 will be selected first and put it into the knapsack so remaining capacity = 80

=>Object 2 with weight 20 and value 30 will be selected at second place so put it into the knapsack so remaining capacity = 60

=>Object 3 with weight 30 and value 66 will be selected now so put it into the knapsack so remaining capacity = 30

=>Now there is no way to select object 4 and object 5 because their weights are more tha remaining capacity.

=>Hence subset of items = {1, 2, 3}

=>Total weigth = 60

=>Total value = 20 + 30 + 66

=>Total value = 116

(3)

Explanation:

=>Using greedy algorithm for 0-1 knapsack by selecting highest density first.

Finding density(v/w):

No	1	2	3	4	5
w	10	20	30	40	50
v	20	30	66	60	55
v/w	2	1.5	2.2	1.5	1.1

=>Order of density: object 3 > object 1 > object 2 = object 4 > object 5

=>Select object 3 with weight 30 and value 66 so put it into knapsack so remaining capacity = 60

=>Select object 1 with weight 10 and value 20 so put it into knapsack so remaining capacity = 50

=>As objects 2 and 4 have equal density so go for higher profit means select object 4 with weight 40 and value 60 so put it into knapsack and remaining capacity = 10

=>There is no way to select object 2 and object 5 because their capacities are more than remaining capacities.

=>Subset of items = {1, 3, 4}

=>Weight = 80

=>Value = 66 + 20 + 60

=>Value = 146

(4)

Explanation:

=>Using greedy algorithm for fractional knapsack by selecting highest density first.

Finding density(v/w):

No	1	2	3	4	5
w	10	20	30	40	50
v	20	30	66	60	55
v/w	2	1.5	2.2	1.5	1.1

=>Order of density: object 3 > object 1 > object 2 = object 4 > object 5

=>Select object 3 with weight 30 and value 66 so put it into knapsack so remaining capacity = 60

=>Select object 1 with weight 10 and value 20 so put it into knapsack so remaining capacity = 50

=>As objects 2 and 4 have equal density so go for higher profit means select object 4 with weight 40 and value 60 so put it into knapsack and remaining capacity = 10

=> Now select object 2 with weight 20 and value 30, break it into 2 parts so value associated with each part is 15 and put one part of weight 10 into knapsack so remaining capacity = 0

=>Subset of items = {1, 2, 3, 4}

=>Weight = 90

=>Value = 66 + 20 + 60 + 15

=>Value = 161

I have explained each and every part of the first question only according to "HOMEWORKLIB RULES when multiple questions are given then only first question needs to be answered" with the help of statements attached to it.