Answered: You are given N cents (integer N) and… | bartleby

Related questions

Question

You are given N cents (integer N) and have to break up the N cents into coins of 1 cent, 2 cents, 5 cents.
Prove that greedy algorithm ALWAYS gives optimal solution

Expert Solution

Step by step

Solved in 4 steps

SEE SOLUTION Check out a sample Q&A here

Blurred answer

Similar questions

A student has been asked to put some parcels on a shelf. The parcels all weigh different amounts, and the shelf has a maximum safe loading weight capacity of 150 Kg. The weight of parcels are as follows (in Kg): The student has been asked to load the maximum weight possible parcels on the shelf subject to the maximum safe loading weight. State two possible approaches for a greedy algorithm solution to solve this problem. In each case, state clearly the result you would get from applying that approach to this problem, stating whether the solution is optimal or not. If your answer does not produce an optimal solution, what algorithm could be employed to find one?
I only need part B in the image, I have already completed part A. How do I formally prove that by using consecutive powers for the values of coins, that it will give me the optimal solution? (using induction preferably unless an easier formal proof is available)
K = 0, L = 18 Write and solve the following linear program using lingo, take screen shots of your model as well as the reports and the optimal solution. Clearly show the optimal solution.NB:K=the second digit of your student number;L=sum of the digits of your student number, For example if your student number is 17400159 thenK=7andL=1+7+4+0+0+1+5+9=27!!!! SAVE YOUR FILE BY YOUR STUDENT NUMBER!!!!minz=t∈T∑(AtYt+PtXt)+k∈K∑(HkUk+BkVk)s.t.Uk+Vk=50∀k∈KXt−CtYt<=0∀t∈Tk∈K∑Vk≥80t∈T∑Xt≥t∈T∑DtXt>=0∀t∈TYt∈{0,1}∀t∈TUk>=0∀k∈KVk>=0∀k∈KThe sets parameters and data are as follows: \[ \begin{array}{l} \mathrm{T}=\{1,2,3,4\} \\ \mathrm{K}=\{0,1,2,3,4\} \\ \mathrm{A}=\{5000,7000,8000,4000\} \\ \mathrm{D}=\{250,65,500,400\} \\ \mathrm{C}=\{500,900,700,800\} \\ \mathrm{P}=\{20, \mathrm{~L}, 25,20\} \\ \mathrm{H}=\{5,3,2, \mathrm{~K}, 9\} \\ \mathrm{B}=\{8,5,4,7,6\} \end{array} \]