1. 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:
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.
Question
Solution Preview
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.
In this version of the problem we can either take an object or not (since it is 0-1 Knapsack). We sort the object in the non-increasing order by their values and we take the corresponding object as long as weight does not exceed 90.This algorithm will take into knapsack: object 3, object 4, and object 2 (we notice it can’t take object 5 after object 4 because the maximum allowed weight would be exceeded).
The achieved weight is 30 + 40 +20 =90.
The achieved value is 66 + 60 + 30 = 156....
By purchasing this solution you'll be able to access the following files:
Solution.docx.
Return to homework library