Maximizing Profit Margin with Greedy Algorithms in CSE331

ConanSam CSE 331 WHN Problem I The goal is to show that the output set has the highest profit margin Let A be the output set of the greedy algorithm and O be an optimal solution Let (I1 ... Ik) be the list of clients in A Let (J1 ... Jm) be the list of clients in O Since O is an optimal solution, the profit margin has to be the highest And since the greedy algorithm selects the client with the highest profit margin for each iteration Therefore the resulting list has to have the highest profit margin for the given potential client list Which shows that selecting the client with the highest profit margin is an optimal greedy choice

Problem 2 XY 2 x exe 2 tht yet The reason why the algorithm is correct is because x to the y can also mean that we multiply x y times, since the algorithm splits the bits in half, we have to combine the lower half and the upper half at the end to get the correct result. Similar to the recursive multiplication algorithm, the recursive power algorithm splits the input y to upper bits and lower bits, once it reaches the stopping condition where the bits cannot be split anymore, the upper bit(s) get multiplied by n times, then the result is multiplied by the lower bit(s).

Problem 3 a b function memotize for is 1 to n do Mci O for it to n do Mci revenue i function select log M i if i 0 return else Assume that the revenue for a log with length n/2 is 15 dollars and the revenue for a log with length n/4 is 10 dollars. If we use the greedy choice from PA1, we would go for the log with length n/2 because it has the highest revenue and profit ratio. However if we consider the total revenue for the truck, the log with length n/4 has a higher profit margin because 10*4 is 40 while 15*2 is only 30. Therefore the greedy algorithm from PA1 is not an optimal solution

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

if ri t ME i MCi i then return i u select log M i i else return select log M i i The algorithm will first memoize the revenue for each feet of log from 1 to n, then it will use the optimal substructure property and create a recursion tree to demonstrate choosing or not choosing a certain log size. The first function uses the overlapping subproblem by memoizing the results so we don't have to recompute them every time. The second function has the optimal substructure property as it generates a recursion tree based on if a Log is being added to the truck or not

WA3

Related Documents