9. (15 points) Dynamic Programming You are given a rod of length n. A rod of...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
9. (15 points) Dynamic Programming You are given a rod of length n. A rod of length j will be sold for P[j] dollars (for 1 j k). Cutting the rod is free. Let R(n) be the maximum earnings by cutting up a rod of length n and selling the pieces. a) (3 points) State a self-reduction from R(n) to its sub-problems. Consider at least a base case of n = 0 and make sure your self-reduction covers all n. b) (2 points) What data structure should be used to store the solutions to sub-problems and what order should the sub-problems be solved? c) (4 points) Write a dynamic programming algorithm based off your self-reduction to calculate the maximum earnings. You do not need to show how to recover the solution. 9. (15 points) Dynamic Programming You are given a rod of length n. A rod of length j will be sold for P[j] dollars (for 1 j k). Cutting the rod is free. Let R(n) be the maximum earnings by cutting up a rod of length n and selling the pieces. a) (3 points) State a self-reduction from R(n) to its sub-problems. Consider at least a base case of n = 0 and make sure your self-reduction covers all n. b) (2 points) What data structure should be used to store the solutions to sub-problems and what order should the sub-problems be solved? c) (4 points) Write a dynamic programming algorithm based off your self-reduction to calculate the maximum earnings. You do not need to show how to recover the solution.
Expert Answer:
Related Book For
Posted Date:
Students also viewed these programming questions
-
CANMNMM January of this year. (a) Each item will be held in a record. Describe all the data structures that must refer to these records to implement the required functionality. Describe all the...
-
Let A, B be sets. Define: (a) the Cartesian product (A B) (b) the set of relations R between A and B (c) the identity relation A on the set A [3 marks] Suppose S, T are relations between A and B, and...
-
"internet radios" for streaming audio, and personal video recorders and players. Describe design and evaluation processes that could be used by a start-up company to improve the usability of such...
-
Plastic Co Pte Ltd (Plastico) is a Fiji company. The company has issued and paid up capital of $250,000 held in equal parts by two brothers. The companys business involves making plastic products for...
-
The Ontario Securities Commission (OSC) found that Zungui Haixi Corporation, a manufacturer of athletic footwear, apparel, accessories, and casual footwear based in China, had fraudulently overstated...
-
Draw the shear and moment diagrams for each member of the frame. Assume the support at A is a pin and D is a roller. 0.8 k/ft B 0.6 k/ft 16 ft -20 ft -
-
Mr. Jenkins, this is typical question: Do you feel that I have treated you fairly in this interview?
-
Georgia Pacific, a manufacturer, incurs the following costs. (1) Classify each cost as either a product or a period cost. If a product cost, identify it as a prime and/or conversion cost. (2)...
-
DataBase managment design. Do the dowsings: 1. Run the sql commands written in ddl.sql file attached 2. Create_a dummy data. You can use "fake data generators" 3. Write followings - Write the query...
-
Imagine that you lend $5,000 to a friend at 7%, and say, "Pay me back when you get a job." Five years later, your friend gets a job and pays you back. Your friend assumed that you meant simple...
-
Part 1 John Wick, a skilled software developer and technology enthusiast, founded his own software consulting firm, TechSolutions, after gaining expertise through years of working in the tech...
-
Grand Teton Inc. own 25% of Grand Canyon Inc. and applies the equity method. During the current Year, Grand Teton sold merchandise with a cost of $120,000 to Grand Canyon for $180,000. At the end of...
-
watch the video below, then submit your response Please respond to the following questions 1. Should the husband have broken into the man's store to steal the drug for his wife? Why or why not? 2....
-
You are given the following information concerning two stocks that make up an index. Assume that the divisor is 2. What is the percentage return for the price-weighted index? Shares Outstanding...
-
Chrome File Edit View History Bookmarks Profiles Tab Window Help Tue Mar 21 5:38 PM PG Campus X Unit 6 Lab A X Do Homewo X Unit 6 Lab C X PUnit 6 Lab C X P Do Homewo X Inbox - chris X Course Hero X...
-
Explain the following proton and carbon 13 resonance spectra corresponding to octyl acetate. Indicate the chemical shift, the equivalent carbons / hydrogens, multiplicity, etc. 1H NMR 13C NMR CAS NO....
-
President Lee Coone has asked you to continue planning for an integrated corporate NDAS network. Ultimately, this network will link all the offices with the Tampa head office and become the...
-
(a) Find the length of the curve y = x4/16 + 1/2x2, 1 x 2 b) Find the area of the surface obtained by rotating the curve in part (a) about the -axis.
-
A bacteria culture initially contains 100 cells and grows at a rate proportional to its size. After an hour the population has increased to 420. (a) Find an expression for the number of bacteria...
-
A tank holds 1000 gallons of water, which drains from the bottom of the tank in half an hour. The values in the table show the volume V of water remaining in the tank (in gallons) after t minutes....
-
A single-tank liquid-level system with inflow rate \(q_{i}\) as its input and liquid level \(h\) as its output is modeled as \(R A \dot{h}+g h=R q_{i}(t), h(0)=0\), where \(R, A, g=\) const. If the...
-
The mechanical system in Figure 8.37, where all parameter values are in consistent physical units, is subject to initial conditions \(x_{1}(0)=1, x_{2}(0)=1, \dot{x}_{1}(0)=-1, \dot{x}_{2}(0)=1\)....
-
A dynamic system is modeled as \[4 \ddot{x}+4 \dot{x}+5 x=10 \sin \left(\frac{1}{2} t ight), \quad x(0)=\frac{1}{2}, \quad \dot{x}(0)=0\] Plot the response \(x(t)\) for \(0 \leq t \leq 20\) by a....
Study smarter with the SolutionInn App