Using Greedy approach. How to create a efficient java code to solve the problem? We want to get from one city, C1, to another, C2. Suppose that a car can travelat most m miles on a full tank. The distance between these two cities is d milesand there are gas stations at distances S₁, S₂,..., S along the way. We assumethat a car starts with a full tank. Compute the minimum number of gas tankrefills to get from one city to another.

The provided Java program uses a Greedy algorithm to determine the minimum number of gas tank…

Answered: Using Greedy approach. How to create a…

Engineering

Computer Science

Using Greedy approach. How to create a efficient java code to solve the problem?

Operations Research : Applications and Algorithms

4th Edition

ISBN:9780534380588

Author:Wayne L. Winston

Publisher:Wayne L. Winston

Chapter18: Deterministic Dynamic Programming

Section18.1: Two Puzzles

Problem 3P

See similar textbooks

Similar questions

09..
Two buses, X and Y, start their journey at the same time on a 950 km route. Bus X gives a 1-hour break after every 3 hours' drive. So, it is at rest at the 4th, 8th, 12th, 16th, 20th, ... hours. Bus Y gives a 1-hour break after every 4 hours' drive. So, it is at rest at the 5th, 10th, 15th, 20th, 25th,... hours. You are given the speeds of the two buses Vx and Vy as 80 and 75, respectively. Write a program that does the following: • Evaluate and display at the end of every hour the distance traveled by each bus. When either one of the buses reach their destination, the evaluations terminate. Depending on whether X or Y or both reach their destination in the last hour, display one of the following messages before stopping (where n is the number of hours): o "Within hour n, bus X reaches its destination." "Within hour n, bus Y reaches its destination." o "Within hour n, both buses reach their destinations." Sample screen output: After hour 1, X is at 80 km, Y is at 75 km. After hour 2, X…
Four individuals wish to traverse an unstable bridge; they all start on the same side. You have 17 minutes to get everyone to the opposite side. Night has fallen, and they have only one torch. Two individuals may cross the bridge at once at most. Any crossing party, whether one or two individuals, must carry a torch. The torch must be carried back and forth; it cannot, for instance, be hurled. Person 1 crosses the bridge in one minute, person 2 in two minutes, person 3 in five minutes, and person 4 in ten minutes. A dyad must trek together at the slower individual's cadence. Create the algorithm specification that solves the problem.
A group of n tourists must cross a wide and deep river with no bridge in sight. They notice two 13-year-old boys playing in a rowboat by the shore. The boat is so tiny, however, that it can only hold two boys or one tourist. How can the tourists get across the river and leave the boys in joint possession of the boat? How many times need the boat pass from shore to shore?
CT ser.
A ski rental agency has n pairs of skis, where the height of the the ipair of skis is s; . There are n skiers who wish to rent skis, where the height of the ith skier is. h;. Ideally, each skier should obtain a pair of skis whose height matches her/his own height as closely as possible. We would like to assign skis to skiers so that the sum of the absolute differences of the heights of each skier and her/his skis is minimized. Design a greedy algorithm for the problem. Prove the correctness of your algorithm. (Hint: Start with two skis and two skiers. How would you match them? Continue to three skis and three skiers, and identify a strategy.)
A detachment of n soldiers must cross a wide and deep river with no bridge in sight. They notice two 12-year-old boys playing in a rowboat by the shore. The boat is so tiny, however, that it can only hold two boys or one soldier. How can the soldiers get across the river and leave the boys in joint possession of the boat? How many times need the boat pass from shore to shore?
Suppose a salesperson is planning a sales trip that includes n cities. Each city is connected to some of the other cities by a road. To minimize travel time, the salesperson wants to determine the shortest route that starts at the salesperson’s home city, visits each of the cities once, and ends up at the home city. This problem of finding the shortest route is called the Travelling Salesperson Problem (TSP) and is a well-known problem that can be solved using Dynamic Programming. Research about the TSP problem and find an algorithm based on Dynamic Programming for that. Explain the approach, the algorithm, and its time complexity. Use an example to explain the way the algorithm operates
You wish to drive from point A to point B along a highway minimizing the time that you are stopped for gas. You are told beforehand the capacity C of you gas tank in liters, your rate F of fuel consumption in liters/kilometer, the rate r in liters/minute at which you can fill your tank at a gas station, and the locations A = x1, ··· , B = xn of the gas stations along the highway. So if you stop to fill your tank from 2 liters to 8 liters, you would have to stop for 6/r minutes. Consider the following two algorithms: (a) Stop at every gas station, and fill the tank with just enough gas to make it to the next gas station. (b) Stop if and only if you don’t have enough gas to make it to the next gas station, and if you stop,fill the tank up all the way. For each algorithm either prove or disprove that this algorithm correctly solves the problem. Your proof of correctness must use an exchange argument.
A ski rental agency has n pairs of skis, where the height of the the ith pair of skis is si . There are n skiers who wish to rent skis, where the height of the ith skier is hi. Ideally, each skier should obtain a pair of skis whose height matches her/his own height as closely as possible. We would like to assign skis to skiers so that the sum of the absolute differences of the heights of each skier and her/his skis is minimized. Design a greedy algorithm for the problem. Prove the correctness of your algorithm. (Hint: Start with two skis and two skiers. How would you match them? Continue to three skis and three skiers, and identify a strategy.)
We are given three ropes with lengths n₁, n2, and n3. Our goal is to find the smallest value k such that we can fully cover the three ropes with smaller ropes of lengths 1,2,3,...,k (one rope from each length). For example, as the figure below shows, when n₁ = 5, n₂ 7, and n3 = 9, it is possible to cover all three ropes with smaller ropes of lengths 1, 2, 3, 4, 5, 6, that is, the output should be k = 6. = Devise a dynamic-programming solution that receives the three values of n₁, n2, and n3 and outputs k. It suffices to show Steps 1 and 2 in the DP paradigm in your solution. In Step 1, you must specify the subproblems, and how the value of the optimal solutions for smaller subproblems can be used to describe those of large subproblems. In Step 2, you must write down a recursive formula for the minimum number of operations to reconfigure. Hint: You may assume the value of k is guessed as kg, and solve the decision problem that asks whether ropes of lengths n₁, n2, n3 can be covered by…
You determine a function f(x) that passes through the points (x0, y0), (x1, y1), ..., (xn, yn) with x0 < x1 < x2...< xn. For some other point x * E (x0, xn), you then use f(x *) to approximate the value of the actual smooth function that underlies the data. This procedure is called: O regression O extrapolation O curve fitting O interpolation