You are going on a long trip. You start on the road at mile post 0. Along the wa

Question

You are going on a long trip. You start on the road at mile post 0. Along the way there are n hotels, at mile posts a1 < a2 < · · · < an, where each ai is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance an), which is your destination. You’d ideally like to travel 200 miles a day, but this may not be possible (depending on the spacing of the hotels). If you travel x miles during a day, the penalty for that day is (200 x)2 . You want to plan your trip so as to minimize the total penalty—that is, the sum, over all travel days, of the daily penalties. Give a dynamic programming algorithm that determines the optimal sequence of hotels at which to stop Can you please give a soultion for this in psudeocode or java?

Explanation / Answer

import java.util.*;

import java.lang.*;

import java.io.*;

class Hotel {

public static void optimalStops(int[] input) {

int[] hotel = input;

int[] bestpath = new int[hotel.length];

int[] stop = new int[hotel.length];

for (int i = 0; i < hotel.length; i++) {

bestpath[i] = (int) (Math.pow((200 - hotel[i]), 2));

stop[i] = 0;

for (int j = 0; j < i; j++) {

if (bestpath[j] + Math.pow((200 - (hotel[i] - hotel[j])), 2) < bestpath[i]) {

bestpath[i] = (int) (bestpath[j] + Math.pow(

(200 - (hotel[i] - hotel[j])), 2));

stop[i] = j + 1;

}

}

}

// Print the output

System.out.println("Minimal Penalty :"+bestpath[hotel.length - 1]);

String finalPath = "";

int index = stop.length-1;

while(index>=0){

finalPath = (index+1)+" "+finalPath;

index = stop[index]-1;

}

System.out.println(Arrays.toString(stop));

System.out.println("Stop at: "+finalPath);

}

/**

* Give the input hotel distances in the trip

*/

public static void main(String[] args) {

int[] input = {190, 420, 550, 660, 670 };

Hotel.optimalStops(input);

}

}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.