有大神共享答案了，穷举法做的： http://blog.csdn.net/siphiababy/article/details/52116246 大神没有加注释，我自己加了注释，希望有用： import java.util.ArrayList; import java.util.List; /** * 用穷举法，列出了所有可能性 * 原理如下： * 比如从左到右总共有20个值（编号1,2,3,...,20），而其中按顺序被选中的只有5个，不考虑别的条件，也就是说，此时要把选中的5个的所有可能心都列出来 * 初始为前五个（1,2,3,4,5）,也就是说，最后最大的5个选择只有（16，17，18，19，20） * 所以之后会有: * 1,2,3,4,6 1,2,3,4,7 1,2,3,4,8 ... 1,2,3,4,20（只有最后一个数字变化） * 1,2,3,5,6 1,2,3,5,7 1,2,3,5,8 ... 1,2,3,5,20 * 1,2,3,6,7 1,2,3,6,8 1,2,3,6,9 ... 1,2,3,6,20 * ... * 1,2,4,5,6 1,2,4,5,7 1,2,4,5,8 ... 1,2,4,5,20 * ... * 根据规律即可写出相应的代码来列举出所有可能 * 可以看出，每行的每个值都只有最后一个数字在变化，所以每行可以看成是一个集合ai；总共的列数又是一个集合A * * 之后根据每行结果中，相邻之间的差d，将不满足要求的ai给remove掉，剩余的集合A就是满足条件的所有情况 * 然后根据A中每个集合元素中的编号，求出最终的最大乘积 */ public class Test_4 { /** * * @param n 总数 * @param k 按顺序选中的人数 * @param d 编号相邻之间的最大差 * @param a n个人，每人的能力值 * @return */ static int com(int n, int k, int d, int[] a) { if (n < k || n <= 0 || k <= 0) { System.out.println("n,k数据输入不合理"); return 0; } //为方便计算，数组坐标从1开始，0不考虑 int[] b = new int[k + 1]; //用来临时存储按先后顺序的k个编号，此时先不考虑编号间的差d int[] fg = new int[k + 1]; //整个数组a中，最大的一种编号顺序，当然是a的最后k个连续的编号 for (int i = 1; i <= k; i++) { b[i] = i; //初始化时候，第一种最小的情况，就是前k个编号 fg[i] = i - k + n; //最大的情况，最后k个编号 } //（具体看原理解释）泛型为集合，是因为根据前面原理描述的，每行存储多种情况，只有最后一个数字变化。列和列之间，也只有一个数字在变化 List<List<Integer>> comList = new ArrayList<>(); while (true) { List<Integer> comp = new ArrayList<Integer>(); for (int i = 1; i <= k; i++) comp.add(b[i]); //把规律计算出的可能性存入当前一行的集合，行（具体看原理解释） comList.add(comp); //放入整个外层集合，列（具体看原理解释） if (b[1] == n - k + 1) //当列完了最后一种最大的情况（就是数组的随后k个编号），则退出循环 break; /** * 此循环的简单解释 * 每种可能中，都从最后一个编号开始计算每种可能性， * 最后一种全都列举完，那就从倒数第二种开始再列每种可能性，此时要考虑的是最后2个编号的变化，依次3个编号的变化。。。 * 最好看最前面原理中示例的演示 */ for (int i = k; i >= 1; i--) { //每次用当前的编号顺序和最大的比 if (b[i] < fg[i]) { b[i]++; //编号顺序的最后一个依次往后递增 for (int j = i + 1; j <= k; j++) //此过程需要根据原理中列举的示例来演示，不好描述 b[j] = b[j - 1] + 1; //后一个起始永远都是前一个加一 break; } } } //从此时开始考虑编号间隔不大于d for (int i = 0; i < comList.size(); i++) { //剔除所有情况中，不满足间隔不大于d的所有情况 List<Integer> cc = comList.get(i); for (int j = 1; j < cc.size(); j++) { if (cc.get(j) - cc.get(j - 1) > d) { //发现有超过d的就移除,移除后，当前cc为空，需要跳出当前内部循环 comList.remove(i); //移除后，外层集合少去一个，顺序发生变化，所以要i=i-1 i = i - 1; break; } } } /** * 下方不需要再具体解释了，一目了然 */ int max = 0; for (int i = 0; i < comList.size(); i++) { int j = 0; int product = 1; while (j < k) { //comList中存储的是每种满足条件的编号序列，可以对应到数组a中取出相应的值 //最初计算编号是按1开始的，所以下方需要-1 product = product * a[comList.get(i).get(j) - 1]; j++; } if (product > max) max = product; } return max; } public static void main(String[] args) { int[] i = {5,10,56,-30,-15,-25,-40,26,15,10}; //测试数据 System.out.println(com(10, 3, 3, i)); } }

点赞回复分享

发布于 2016-08-05 02:41