We have 5 objects, and the weights and values are No. 1 2 3 4 5 w 10 20 30 40 50
ID: 666230 • Letter: W
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 60 55
The knapsack can carry a weight not exceeding 90, find a subset items and give the total weight and value for following algorithms:
* By using the algorithm of greedy of value for 0-1 knapsack problem? By selecting the highest value first.
* By using the algorithm of greedy of weight for 0-1 knapsack problem? By selecting lightest item first.
* 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
Thank you for your help.
Explanation / Answer
Let the weight of the knapsack be denoted by W and the value of the items in it be represented by V.
Initially the value of both W and V is 0.
Let the capacity of the knapsack be denoted by C.
Initially the value of C is 90.
The items are selected from the given item set.
Since the algorithm is for a 0-1 knapsack, an item must be picked with its full weight.
No fractional weights are allowed.
The algorithm works by selecting the item with the highest value first.
The working of the algorithm is as follows:
Step 1:
The item no. 3 is added to the knapsack.
The value of the item no. 3 is added to V.
New value of V is 66.
The weight of the item no. 3 is subtracted from W.
New value of W is 30.
The item no. 3 is removed from the set of items.
Step 2:
The item no. 4 is added to the knapsack.
The value of the item no. 4 is added to V.
New value of V is 126.
The weight of the item no. 4 is subtracted from W.
New value of W is 70.
The item no. 4 is removed from the set of items.
Step 3:
The next item with highest value is the item no. 5, but adding its weight to the value of W exceeds the capacity of the knapsack so it is not added to the knapsack.
The next item with the highest value is the item no. 2.
The item no. 2 is added to the knapsack.
The value of item no. 2 is added to V.
New value of V is 156.
The weight of the item no. 2 is subtracted from W.
New value of W is 90.
The weight of the items in the knapsack is now equal to the capacity of the knapsack.
No more items can now be inserted into the knapsack.
{No. 3, No. 4, No. 2}
The lightest item is picked first.
The order in which the items are picked is as follows:
Item no. 1, Item no. 2, Item no. 3.
After the insertion of item no. 3 in the knapsack, the weight of the items inside the knapsack becomes 60 and no more items can now be added to the knapsack.
{No. 1, No. 2, No. 3}
The density of the given items is calculated by using the following formula:
Density = Weight of the item / Value of the item
The density of the items is shown in the following table:
Item
Density(w/v)
No.1
2.0
No. 2
1.5
No. 3
2.2
No. 4
1.5
No. 5
1.1
The highest density item is picked first.
The order in which the items are picked is as follows:
Item no. 3, Item no. 1, Item no. 2.
After the insertion of item no. 2 into the knapsack, the total weight of the items inside the knapsack becomes 60 and no more items can now be added to the knapsack.
{No. 3, No. 1, No. 2}
In a fractional knapsack algorithm, it is not necessary to add the whole item to the knapsack.
If required even a fraction of the item can be inserted.
The density of the items is shown in the following table:
Item
Density(w/v)
No.1
2.0
No. 2
1.5
No. 3
2.2
No. 4
1.5
No. 5
1.1
The item with the highest density is picked first.
The order in which the items are added is as follows:
Item no. 3, Item no. 1, Item no. 2, Item no. 4
After the insertion of the item no. 2 into the knapsack, the weight of the items inside the knapsack becomes 60. No more whole item can now be inserted into the knapsack but we can break down the item and add a fraction of it to the knapsack. Since, the next highest density item is the item no. 4, we can pick only the fraction of the item no. 4 which weighs exactly 30 (Since, only 30 more weight can be added to the knapsack).
We divide the required weight by the weight of the item to get the fraction of the item that can be added to the knapsack.
The required fraction of the item no. 4 is as follows:
30 / 40 = 0.75.
So. 0.75 fraction of the item no. 4 is added to the knapsack. The value of this fraction can be calculated by multiplying it with the total value of the item.
The value of 0.75 fraction of item no. 4 is as follows:
0.75 * 60 = 45.
{No. 3, No. 1, No. 2, No. 4}
Item
Density(w/v)
No.1
2.0
No. 2
1.5
No. 3
2.2
No. 4
1.5
No. 5
1.1
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.