There are two parallel lines of apples, Line 0 and Line 1, each of length T...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
There are two parallel lines of apples, Line 0 and Line 1, each of length T meters. In each line, every 1 meter there is either: a good apple or a bad apple For example, if N = 11, the lines might look like the figure below: Meter: 1 2 3 4 5 67 8 9 10 11 Line 0: Line 1: You are designing an apple collecting robot. Your robot starts at meter 1 of Line 0, and then slowly moves to the right, collecting apples along the way. The robot can switch between the lines, but at each meter, it can collect only one apple. More precisely, if the robot switches from Line 0 to Line 1 at meter 4, then it collects the apple at Line 1 (and not the apple at Line 0). Your goal is for the robot to collect as many good apples as possible. However, switching between Lines 0 and 1 costs a lot of energy for your robot, and so your robot can only switch from one line to the other at most s times. For a concrete example, suppose in the example above that the robot starts in Line 0 and can switch at most two times (s=2). It might decide to switch at meter 4 (from Line 0 to Line 1) and again at meter 9 (from Line 1 to Line 0). In total, it collects 9 good apples. It is happy. Now, suppose that the two lines of apples are visible to the robot and that s is known. The "data" (the lines of apples) are given as a 2D array X, where, for meters m = 1,2,..., N and lines j = 0, 1, we have X[j, m] = if Line j has a good apple at meter m; 0 if Line j has a bad apple at meter m. In this problem, we will use dynamic programming to devise an algorithm for collect- ing the optimal number of good apples; here, "optimal" means maximum. To get you started, consider the following subproblem: The optimal number of good apples that can be collected when starting in Line j at meter m and going till the end (meter N) when k more switches are possible. (a) Using the subproblem suggested above, write a recurrence to express the optimal reward (number of collected good apples) of a larger problem in terms of the optimal reward of subproblems. (b) Using your recurrence, write a dynamic programming algorithm for finding the optimal reward when starting at meter 1 of Line 0 with a budget of s 20 switches. It is ok if your algorithm does not have an efficient runtime. In dynamic programming, there is a clever trick called "memoization" (we will learn about it later in the course) which ensures that a given algorithm never makes the same recursive call twice (i.e., once it has obtained the optimal reward for a subproblem, it stores it and neve recomputes it again). (c) Once you have filled the table of optimal rewards for subproblems, describe a way to figure out in exactly which meters the robot should switch. That is, construct an optimal solution. There are two parallel lines of apples, Line 0 and Line 1, each of length T meters. In each line, every 1 meter there is either: a good apple or a bad apple For example, if N = 11, the lines might look like the figure below: Meter: 1 2 3 4 5 67 8 9 10 11 Line 0: Line 1: You are designing an apple collecting robot. Your robot starts at meter 1 of Line 0, and then slowly moves to the right, collecting apples along the way. The robot can switch between the lines, but at each meter, it can collect only one apple. More precisely, if the robot switches from Line 0 to Line 1 at meter 4, then it collects the apple at Line 1 (and not the apple at Line 0). Your goal is for the robot to collect as many good apples as possible. However, switching between Lines 0 and 1 costs a lot of energy for your robot, and so your robot can only switch from one line to the other at most s times. For a concrete example, suppose in the example above that the robot starts in Line 0 and can switch at most two times (s=2). It might decide to switch at meter 4 (from Line 0 to Line 1) and again at meter 9 (from Line 1 to Line 0). In total, it collects 9 good apples. It is happy. There are two parallel lines of apples, Line 0 and Line 1, each of length T meters. In each line, every 1 meter there is either: a good apple or a bad apple For example, if N = 11, the lines might look like the figure below: Meter: 1 2 3 4 5 67 8 9 10 11 Line 0: Line 1: You are designing an apple collecting robot. Your robot starts at meter 1 of Line 0, and then slowly moves to the right, collecting apples along the way. The robot can switch between the lines, but at each meter, it can collect only one apple. More precisely, if the robot switches from Line 0 to Line 1 at meter 4, then it collects the apple at Line 1 (and not the apple at Line 0). Your goal is for the robot to collect as many good apples as possible. However, switching between Lines 0 and 1 costs a lot of energy for your robot, and so your robot can only switch from one line to the other at most s times. For a concrete example, suppose in the example above that the robot starts in Line 0 and can switch at most two times (s=2). It might decide to switch at meter 4 (from Line 0 to Line 1) and again at meter 9 (from Line 1 to Line 0). In total, it collects 9 good apples. It is happy. Now, suppose that the two lines of apples are visible to the robot and that s is known. The "data" (the lines of apples) are given as a 2D array X, where, for meters m = 1,2,..., N and lines j = 0, 1, we have X[j, m] = if Line j has a good apple at meter m; 0 if Line j has a bad apple at meter m. In this problem, we will use dynamic programming to devise an algorithm for collect- ing the optimal number of good apples; here, "optimal" means maximum. To get you started, consider the following subproblem: The optimal number of good apples that can be collected when starting in Line j at meter m and going till the end (meter N) when k more switches are possible. (a) Using the subproblem suggested above, write a recurrence to express the optimal reward (number of collected good apples) of a larger problem in terms of the optimal reward of subproblems. (b) Using your recurrence, write a dynamic programming algorithm for finding the optimal reward when starting at meter 1 of Line 0 with a budget of s 20 switches. It is ok if your algorithm does not have an efficient runtime. In dynamic programming, there is a clever trick called "memoization" (we will learn about it later in the course) which ensures that a given algorithm never makes the same recursive call twice (i.e., Now, suppose that the two lines of apples are visible to the robot and that s is known. The "data" (the lines of apples) are given as a 2D array X, where, for meters m = 1,2,..., N and lines j = 0, 1, we have X[j, m] = if Line j has a good apple at meter m; 0 if Line j has a bad apple at meter m. In this problem, we will use dynamic programming to devise an algorithm for collect- ing the optimal number of good apples; here, "optimal" means maximum. To get you started, consider the following subproblem: The optimal number of good apples that can be collected when starting in Line j at meter m and going till the end (meter N) when k more switches are possible. (a) Using the subproblem suggested above, write a recurrence to express the optimal reward (number of collected good apples) of a larger problem in terms of the optimal reward of subproblems. (b) Using your recurrence, write a dynamic programming algorithm for finding the optimal reward when starting at meter 1 of Line 0 with a budget of s 20 switches. It is ok if your algorithm does not have an efficient runtime. In dynamic programming, there is a clever trick called "memoization" (we will learn about it later in the course) which ensures that a given algorithm never makes the same recursive call twice (i.e., once it has obtained the optimal reward for a subproblem, it stores it and neve recomputes it again). (c) Once you have filled the table of optimal rewards for subproblems, describe a way to figure out in exactly which meters the robot should switch. That is, construct an optimal solution. once it has obtained the optimal reward for a subproblem, it stores it and neve recomputes it again). (c) Once you have filled the table of optimal rewards for subproblems, describe a way to figure out in exactly which meters the robot should switch. That is, construct an optimal solution.
Expert Answer:
Answer rating: 100% (QA)
Understanding the Problem The robot moves on two parallel lines Line 0 and Line 1 of apple trees each T meters long Every meter on a line has either a ... View the full answer
Related Book For
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill
Posted Date:
Students also viewed these programming questions
-
answer all questions as instructed below. attend all questions. 4 Computer Vision (a) Explain why such a tiny number of 2D Gabor wavelets as shown in this sequence are so efficient at representing...
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
Valuing Preferred Stock Best Rate Bank just issued some new preferred stock. The issue will pay a $10 annual dividend in perpetuity, beginning 10 years from now. If the market requires a 7 percent...
-
How should a firm decide what industry it is in? Discuss.
-
What are the four commonly referred to consumer rights?
-
On February 20, 2009, Cedar Valley Aviation, a wholly owned subsidiary of Aerial Services, Inc. (ASI), brought a Piper 522AS (Cheyenne II) in for maintenance to Des Moines Flying Service, Inc....
-
The following material relates to Darrow Company: Required Place an X in the appropriate columns for each of thesituations. Cash Flows Classification Noncash Effect on Cash Operating Investing...
-
X The function h is defined as h(x)=4-x2 x ln x, x>1 jh(x) Show that h(x) dx = 4ln 2- -1 15 16
-
Trini Company set the following standard costs per unit for its single product Direct materials (30 pounds @ $5.10 per pound) Direct labor (8 hours @ $14 per hour) Variable overhead (8 hours@ $6 per...
-
The following data is from Chase Corporation's accounting records for the year ended 2019: Sales $930,000 Raw material inventory starting at $70,000 Raw material inventory ending in $40,000 Raw...
-
A helicopter flies with an airspeed of 42.5 m/s [W]. If the wind is traveling with a velocity of 25.0 m/s [E 30 S] relative to the ground then determine the velocity of the helicopter relative to the...
-
start a male underwear brand 1. name the underwear brand and tagline 2. what are your brand colors? 3. how would you sell your underwear? 4. ways to promote your underwear brand? 5. pricing? high-end...
-
An object moves in one dimensional motion with constant acceleration a = 7.9 m/s. At time t = Os, the object is at x0 = 4.7 m and has an initial velocity of vo = 4.6 m/s. How far will the object move...
-
There are three different levels of burden of proof for different matters. In criminal cases, the burden is beyond a reasonable doubt. In most civil cases, the burden is a preponderance of the...
-
Business: Meals in a Jar Location: Daet, Cam Norte On your own words create the ff: Marketing Plan in terms of: Present Market Situation Competitors Target Market (in terms of demographic,...
-
Use the complex form to find the Fourier integral representation of the function. [3 |x| <1 f(x) = { 0 x>1
-
Which of the ocean zones shown would be home to each of the following organisms: lobster, coral, mussel, porpoise, and dragonfish? For those organisms you identify as living in the pelagic...
-
Quince Interests is a partnership with a tax year that ends September 30, 2012. During that year, Potter, a partner, received $3,000 per month as a guaranteed payment, and his share of partnership...
-
Your supervisor has asked you to research the following situation concerning Owen and Lisa Cordoncillo. Owen and Lisa are brother and sister. In May 2012, Owen and Lisa exchange business pickup...
-
Fisafolia Corporation has gross income from operations of $220,000 and operating expenses of $160,000 for 2012. The corporation also has $20,000 in dividends from publicly traded domestic...
-
Within the context of Exercise 1, let \(\|X\|_{r}\) be defined for \(X \in X_{r}\) as \[\|X\|_{r}=\left[\int_{\Omega}|X(\omega)|^{r} d P(\omega)ight]^{1 / r}\] Prove that \(\|X\|_{r}\) is a norm....
-
Let \(\left\{X_{n}ight\}_{n=1}^{\infty}\) be a sequence of random variables where \(X_{n}\) has distribution \(F_{n}\) which has mean \(\theta_{n}\) for all \(n \in \mathbb{N}\). Suppose that \[\lim...
-
Let \(\left\{X_{n}ight\}_{n=1}^{\infty}\) be a sequence of independent random variables where \(X_{n}\) has a Triangular \(\left(\alpha_{n}, \beta_{n}, \gamma_{n}ight)\) distribution for all \(n \in...
Study smarter with the SolutionInn App