Data Structure and Algorithm Analysis Greedy strategy a. Does using the greedy a
ID: 3586549 • Letter: D
Question
Data Structure and Algorithm Analysis
Greedy strategy a. Does using the greedy algorithm for making change of n cents give a correct solution if a nickel was worth 6 cents instead of 5? (we have 1, 6, 10 and 25 cent coin denominations). b. ,n, each item has a weight wi > 0 and value v we have n unique items. For i = 12.3 0. Write a greedy algorithm to find the maximum value of items that can be carried in a knapsack with a maximum weight capacity of W. An item may be broken into pieces and only a fraction put into the knapsack. It should take an array of weights, an array of item values and the weight limit of the knapsack as input. The array of weights and items are ordered such that w, corresponds to the same item as v,Explanation / Answer
ANSWER:
Greedy strategy :
a) Greedy algorithm for coin change:
No, the greedy algorithm does not create the correct solution with coin denominations 1, 6, 10 and 25 cents.
Explanation:
Let us consider the change for rupees 12. To make the change, the greedy algorithm produce solution as (10, 1, 1). But the optimal solution is (6, 6) uses 2 coins.
b) Greedy algorithm for FRACTIONAL KNAPSACK PROBLEM:
Algorithm:
FractionalKnapsackAlgorithm (w [1 . . n] , v [1 . . n] , W)
//For loop to initialize weightAry for kk = 1 to n
//Set the current element to 0. weighAry(kk] = 0
//End for Loop end
//Set value tmpWeight = 0
//For loop for kk = 1 to n
//Check if it is possible to inclue the current item as a hole if tmpWeight + w(kk] S W then
//Set the value weighAry(kk] = 1
//Include the current item
tmpWeight = tmpWeight + w[kk]
//If current item cant be fitted fully, then add the partial item else
//Find the partial amount to add weighAry[kk] = (W - tmpWeight) / w[kk]
//Set value tmpWeight = W
//Break break
//If end end
//Loop end end
//Return. return weighAry
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.