We have 5 objects, and the weights and values are No. 1 2 3 4 5 w 10 20 30 40 50

Question

We have 5 objects, and the weights and values are

No.      1          2          3          4          5

w         10        20        30        40        50

v          20        30        66        40        60

The knapsack can carry a weight not exceeding 100, 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.

By using the algorithm of greedy of density for fractional knapsack problem? By selecting the highest density item first.

Explanation / Answer

1) Your order of selection would be 3,5,2. Since you keep adding objects in greedy by value way, you select values 66 and 50 and reach a combined weight of 80. Going by greedy by value further you would like to pick up value 40 but combined weight then would exceed 100 so you go for the next best and choose value 30 whereby you reach your limit of combined weight 100 and stop.

2) Your order of selection would be 1,2,3,4. Since you keep adding objects in greedy by lower weight way, you select weights 10, 20, 30, 40 until you reached combined weight of 100 here and stop.

3)

Going by the question and above problems. Density here may be defined as the value/weight of the objects. We want density of value. That is since it would be ideal to think for us to have more value in less weight since our goal is to have most value however we getting constricted by the limit of 100 for weight. There by when we select items of highest density (provided in the table above), we get most value in the limit of 100 weight.

Your order of selection would be 3,1,2,4. Since you keep adding objects in greedy by density way, you select objects 3,1,2 and reach a combined weight of 60. Going by greedy by density further you would like to pick up object 5 with next higher density of 1.2 but combined weight then would exceed 100 so you go for the next best and choose object 4 whereby you reach your limit of combined weight 100 and stop.

4) In case of Fractional Knapsack Problem, your selection order would be 3,1,2,5. Since in this case you are not limited by the absolute weight of 50. You can choose a fraction of it so that you can take the remaining 40 weight which you can bear. Value added by fraction of Object 5 would be 1.2*40=48.

P.s. Feel free to ask doubts!

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.