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
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 an efficient algorithm that determines the optimal sequence of hotels at which to stop. Here is the input file:
66
83
99
104
109
164
263
266
276
306
337
343
418
432
462
489
558
590
620
672
719
741
752
823
919
977
994
1004
1086
1088
1117
1130
1219
1245
1289
1357
1436
1519
1525
1560
1597
1678
1703
1795
1885
1921
1976
2012
2046
2126
2209
2261
2355
2403
2478
2559
2605
2704
2758
2796
2859
2881
2957
2998
3076
3098
3188
3232
3260
3334
3427
3524
3596
3611
3646
3722
3764
3790
3863
3867
3932
3993
4001
4026
4094
4156
4199
4228
4271
4355
4386
4454
4551
4559
4578
4674
4735
4746
4833
4905
Your program should read in a file like the above and create a corresponding output file, HW1Output.txt, that lists the mile posts of an optimal trip from the 0 mile post to the final mile post, along with the total penalty that has accumulated at each stop (It should look like this):
Distance: 0 Total Penalty: 0
Distance: 164 Total Penalty: 1296
Distance: 343 Total Penalty: 1737
Distance: 558 Total Penalty: 1962
Distance: 741 Total Penalty: 2251
Distance: 919 Total Penalty: 2735
Distance: 4735 Total Penalty: 8639
Distance: 4905 Total Penalty: 9539
With one hundred or more stops to consider, it is impossible for the program to finish in a reasonable amount of time if it uses a straightforward brute-force search that explicitly considers every possible combination of stops. For this assignment, you are required to use a dynamic programming solution.Your program (in Java) should be flexible enough to handle input files of various lengths (I would recommend using an ArrayList).
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started