import java.util.*;
public class OptimalTravel {
public static OptimalSightseeingResult selectOptimalSights(List<Sightseeing> sights, int totalTime) {
Collections.sort(sights, new Comparator<Sightseeing>() {
@Override
public int compare(Sightseeing s1, Sightseeing s2) {
double ratio1 = (double) s1.rating / s1.time;
double ratio2 = (double) s2.rating / s2.time;
if (ratio1 < ratio2) {
return 1;
} else if (ratio1 > ratio2) {
return -1;
} else {
return 0;
}
}
});
List<Sightseeing> selectedSights = new ArrayList<>();
int totalRating = 0;
for (Sightseeing sight : sights) {
if (sight.time <= totalTime) {
selectedSights.add(sight);
totalTime -= sight.time;
totalRating += sight.rating;
}
}
return new OptimalSightseeingResult(selectedSights, totalRating);
}
public static void main(String[] args) {
List<Sightseeing> sights = new ArrayList<>();
sights.add(new Sightseeing("故宫", 1, 7));
sights.add(new Sightseeing("颐和园", 2, 8));
sights.add(new Sightseeing("长城", 3, 9));
sights.add(new Sightseeing("天坛", 1, 6));
int totalTime = 4;
OptimalSightseeingResult result = selectOptimalSights(sights, totalTime);
System.out.println("去以下景点能够获得最大价值:");
for (Sightseeing sight : result.selectedSights) {
System.out.println(sight.name);
}
System.out.println("总评分:" + result.totalRating);
}
}
class OptimalSightseeingResult {
List<Sightseeing> selectedSights;
int totalRating;
public OptimalSightseeingResult(List<Sightseeing> selectedSights, int totalRating) {
this.selectedSights = selectedSights;
this.totalRating = totalRating;
}
}
class Sightseeing {
String name;
int time;
int rating;
public Sightseeing(String name, int time, int rating) {
this.name = name;
this.time = time;
this.rating = rating;
}
}