风机离升压站的距离,如 30 20 35 40
风机发电量,如 20 18 25 30
输电总距离的限制,如50
输送电量的最大值
30 20 35 40 20 18 25 30 50
38
距离,发电量,总距离各起一行,数组间以空格分隔
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { /** * 链接:https://www.nowcoder.com/questionTerminal/dee7a45562324d9a8e2bc7f0e4465bfc * [编程题]风电场风机发电调度问题 * <p> * 某风电场每台风机的发电量和距离升压站的距离各不相同, * <p> * 如风机1:发电量30,距离20;风机2:发电量35,距离25;风机3:发电量25,距离18……, * <p> * 要求在输电总距离限定(如小于100)的前提下,选择风机向升压站输电,使得输送的电量最大。 */ public static void main(String[] args) { Scanner input = new Scanner(System.in); List<List<Integer>> data = new ArrayList<>(); while (input.hasNextLine()) { String line = input.nextLine(); String[] values = line.split(" "); List<Integer> lineData = new ArrayList<>(); for (String value : values) { lineData.add(Integer.valueOf(value)); } data.add(lineData); } List<Integer> distances = data.get(0); List<Integer> powers = data.get(1); int maxDist = data.get(2).get(0); Main s = new Main(); System.out.println(s.getMaxResult(distances, powers, maxDist)); } private int getMaxResult(List<Integer> distances, List<Integer> powers, int maxDist) { if (distances.size() == 0 || maxDist == 0) return 0; int[][] dp = new int[distances.size()][maxDist + 1]; for (int i = 0; i < dp.length; i++) { int dist = distances.get(i); int power = powers.get(i); for (int j = 0; j <= maxDist; j++) { if (dist <= j) { if (i == 0) { dp[i][j] = power; } else { dp[i][j] = Integer.max(dp[i - 1][j - dist] + power, dp[i - 1][j]); } } else { if (i > 0) { dp[i][j] = dp[i - 1][j]; } } } } return dp[dp.length - 1][maxDist]; } }