package algorithm; import java.util.ArrayList; import java.util.Comparator; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.Map.Entry; import java.util.Random; import java.util.TreeMap; /** * * @Description: n个数按顺序分成m组,每组和尽量相近 * 思路:先递归求出所有切分点的组合方式,然后分别计算每组中的和,对每组和两两差值的绝对值累加,最小的为最优切分点。 * 如:{1,2,3,4}分2组 可以{1}和{2,3,4} {1,2}和{3,4} {1,2,3}和{4} 不能为{1,3}{2,4} * 缺点:当list很大,分的组很多的时候,效率很低,几十分钟才能算出来。 * @author thrillerzw * @version 1.0 * @create time 2014-4-28 下午6:47:19 */ public class TestCombination { public static void main(String[] args) { List<Integer> lengthList = new ArrayList<Integer>(); for(int i=0;i<6;i++){ lengthList.add(new Random().nextInt(100)); } long startTime=System.currentTimeMillis(); int m = 3; List<List<Integer>> resultList = new ArrayList<List<Integer>>(); if (lengthList.size() < m) { buildResultList(resultList, lengthList); } else { int endIndex = lengthList.size() - (m - 2); int[] tempArr = new int[m - 1]; List<int[]> combList = new ArrayList<int[]>(); int num = -1; //所有切分点的组合存入combList Combine(lengthList, m - 1, tempArr, 0, 0, combList); int[] resultArr = null; for (int[] combArr : combList) { for (int i = 0; i < combArr.length; i++) { System.out.print(combArr[i] + " "); } System.out.println(); int[] sumArr = getSum(combArr, lengthList); int diffSum = computeDifferent(sumArr); if (diffSum < num || num == -1) { num = diffSum; System.out.println("num=" + num); resultArr = combArr; } } if (resultArr != null) { for (int result : resultArr) { System.out.print(result + " "); } } buildResultList(resultList, lengthList, resultArr); } long endTime=System.currentTimeMillis(); long useTime=endTime-startTime; System.out.print(lengthList.size()+"个数分为"+m+"组使用毫秒时间"+useTime+" resultList=" + resultList); } //如果分组数m大于等于集合的长度。 static void buildResultList(List<List<Integer>> resultList, List<Integer> dataList) { for (int i = 0; i < dataList.size(); i++) { List<Integer> list = new ArrayList<Integer>(); list.add(dataList.get(i)); resultList.add(list); } } // 根据最优切分点构建结果集 static void buildResultList(List<List<Integer>> resultList, List<Integer> dataList, int[] resultArr) { if (resultList == null || dataList == null || resultArr == null) { return; } int j = 0; int maxJ = 0; for (int i = 0; i <= resultArr.length; i++) { if (i == resultArr.length) { maxJ = dataList.size(); } else { maxJ = resultArr[i]; } List<Integer> list = new ArrayList<Integer>(); for (; j < maxJ; j++) { list.add(dataList.get(j)); } resultList.add(list); } } //每种组合不同段的和。比如0--2 2--5 5--list的结尾 static int[] getSum(int[] combArr, List<Integer> dataList) { if (combArr == null || dataList == null) { return null; } int[] sumArr = new int[combArr.length + 1]; int j = 0; int sum = 0; int maxJ = 0; for (int i = 0; i <= combArr.length; i++) { if (i == combArr.length) { maxJ = dataList.size(); } else { maxJ = combArr[i]; } for (; j < maxJ; j++) { sum += dataList.get(j); } sumArr[i] = sum; System.out.println("sum=" + sum); sum = 0; } return sumArr; } // 数组中值两两比较,差的绝对值的和累加 static int computeDifferent(int[] sumArr) { int diffSum = 0; for (int i = 0; i < sumArr.length; i++) { for (int j = i + 1; j < sumArr.length; j++) { diffSum += Math.abs(sumArr[i] - sumArr[j]); } } System.out.println("diffSum=" + diffSum); return diffSum; } // 所有切分点组合 private static void Combine(List<Integer> lengthList, int num, int[] tempArr, int tempArrIndex, int low, List<int[]> combList) { if (lengthList == null || lengthList.size() < num) { return; } if (num == 0) { if (tempArr[tempArr.length - 1] != lengthList.size()) { combList.add(tempArr); } } else { for (int i = low; i < lengthList.size(); i++) { tempArr[tempArrIndex] = i + 1; Combine(lengthList, num - 1, tempArr, ++tempArrIndex, i + 1, combList); int[] newTempArr = new int[tempArr.length]; System.arraycopy(tempArr, 0, newTempArr, 0, tempArr.length - 1); tempArr = newTempArr; tempArrIndex--; } } } }
2、
package algorithm; import java.util.ArrayList; import java.util.List; /** * * @Description: 按顺序累加,与平均值相差最小的分为一组。 * 优点:解决数据、分组大时候,穷举所有组合效率低的问题。适合数据比较均匀的时候。 * 缺点:大数集中分布到一头等特殊情况分组不好。 * @author thrillerzw * @version 1.0 * @create time 2014-4-30 上午9:52:16 */ public class TestAverage { public static void main(String[] args) { List<Integer> lengthList = new ArrayList<Integer>(); lengthList.add(1); lengthList.add(2); lengthList.add(8); lengthList.add(6); lengthList.add(4); lengthList.add(10); int m = 3; List<List<Integer>> resultList = new ArrayList<List<Integer>>(); if (lengthList.size() < m) { buildResultList(resultList, lengthList); } else { int[] pointArr = findSplitPoint(lengthList, m); buildResultList(resultList, lengthList, pointArr); } System.out.print("resultList=" + resultList); } private static int[] findSplitPoint(List<Integer> lengthList, int m) { int totalNum = 0; for (int i = 0; i < lengthList.size(); i++) { totalNum += lengthList.get(i); } //平均值 double average = (double) totalNum / (double) m; System.out.println("average=" + average); int groupNum = 0; int[] pointArr = new int[m - 1]; int pointArrIndex = 0; double minDiffSum = -1; int i = 0; for (; i < lengthList.size(); i++) { int num = lengthList.get(i); //按顺序累加 groupNum += num; double curDiffSum = Math.abs(groupNum - average); int surplusGroupNum = m - 1 - pointArrIndex; int surplusDataNum = lengthList.size() - i; int differNum = surplusDataNum - surplusGroupNum; if (differNum > 0) { //当前累加 与平均值的距离 < 上次累加与平均值的距离 if (curDiffSum < minDiffSum || minDiffSum == -1) { minDiffSum = curDiffSum; } else { //保存切分点 pointArr[pointArrIndex] = i; if (pointArrIndex == m - 2) { break; } pointArrIndex++; groupNum = num; minDiffSum = Math.abs(num - average); } } else { //简单解决大数分布到头尾,不够分组的情况。把末尾的每个值单独分为一组。 pointArr[pointArrIndex++] = i; int point = i + 1; for (int j = 0; j < surplusGroupNum - 1; j++) { pointArr[pointArrIndex++] = point++; } break; } } return pointArr; } static void buildResultList(List<List<Integer>> resultList, List<Integer> dataList) { for (int i = 0; i < dataList.size(); i++) { List<Integer> list = new ArrayList<Integer>(); list.add(dataList.get(i)); resultList.add(list); } } static void buildResultList(List<List<Integer>> resultList, List<Integer> dataList, int[] resultArr) { if (resultList == null || dataList == null || resultArr == null) { return; } int j = 0; int maxJ = 0; for (int i = 0; i <= resultArr.length; i++) { if (i == resultArr.length) { maxJ = dataList.size(); } else { maxJ = resultArr[i]; } List<Integer> list = new ArrayList<Integer>(); for (; j < maxJ; j++) { list.add(dataList.get(j)); } resultList.add(list); } } }
相关推荐
分治算法求n个数的数组中找出第二个最大元素
此代码实现从N个数字中取出M个数字的所有组合,有两种实现方法,递归方法和非递归方法。
请设计算法完成螺旋阵的输出,具有要求为:输入一个m行n列的矩阵,按顺时针螺旋顺序输出矩阵中的所有元素。 【输入】 第1行输入两个正整数m和n,表示m行n列的矩阵; 从第2行开始按行输入该矩阵的所有元素。 【输出】...
对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数 最小的删数方案。 «编程任务: 对于给定的正整数a,编程计算删去k个数字后得到的最小数。 Input 由文件input.txt提供输入数据。文件的第1...
分治算法思想,将n位X和Y分成2段,每段n/2位。则X分为AB两段,Y分为CD两段。 有X=A*(10)^(n/2)+B,Y=C*(10)^(n/2)+D;XY=(A*(10)^(n/2)+B)(C*(10)^(n/2)+D)=AC*(10)^n+(AD+BC)*(10)^(n/2)+BD。 证明及详细分析参见...
excel文档,可以任意生成m选n的全部组合,速度还可以。
数据结构教程(JAVA语言描述) 设计一个算法,将含有n个整数元素的数组a[0..n-1]循环右移m位,要求算法的空间复杂度为O(1)
这是一个用C++写的简单算法,里面没用到什么高深的东西,就是基本的控制语句组成。
全排列是将一组数按一定顺序进行排列,如果这组数有n个,那么全排列数为n!个。现以{1, 2, 3, 4, 5}为 例说明如何编写全排列的递归算法。 1、首先看最后两个数4, 5。 它们的全排列为4 5和5 4, 即以4开头的5的全排列...
(3) 能输入每个进程的最大资源要求 模拟利用银行家算法为进程的若干次资源请求分配资源 (4) 输入本次资源要求; (5) 按银行家算法为进程分配资源,本次分配是否成功要显示出来(要能处理各种情况:可以满足这次请求、...
功能: 丢手帕 说明: m个小孩围 坐一起.从第一个小孩从1开始数数.数到n的小孩出局.下一个小孩子从1开始数.问最终小孩出列的顺序.
可输入多组测试数据(不超过50组测试数据),每组测试数据分两行,每行一个数,数的含义如下。 第一行:正整数a(a是大于0的一个n位正整数) 第二行:正整数k 以0来结束测试数据。 输出格式 输出每组测试数据所...
这个题目有个最容易想到的n*log10(n)的算法。这是自己写的复杂度为O(n*log10(n))的代码: void statNumber(int n) { int i, t; int count[10] = {0}; for(i = 1; i <= n; i++) { t = i; while(t) { ...
已知有两个按元素值递增有序的顺序表A和B,设计一个算法将表A和表B的全部元素归并为一个按元素值递增有序的顺序表C。
输入N,输出1-N全排列c语言算法,非递归算法................
试设计一个算法,计算出从三角形 的顶至底的一条路径,使该路径经过的数字总和最大。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 编程任务: 对于给定的由n 行数字组成的数字三角形,编程计算从三角形的顶至底的路径...
本代码为完整的运行程序,算法包含于程序块中,同学可以直接拿去使用! 本代码以最简洁的方式向大家解决了此问题,相信99%的同学都能看懂,如有任何疑问,可以私聊我!希望对各位同学有所帮助!
6位数,共有几种排列组合的算法,java实现
设计一个n个并发进程共享m个系统资源的程序以实现银行家算法。要求: 1) 简单的选择界面; 2) 能显示当前系统资源的占用和剩余情况。 3) 为进程分配资源,如果进程要求的资源大于系统剩余的资源,不与分配并且...
//稀疏矩阵的三元组顺序表存储表示 #define MAXSIZE 100 //非零元个数最大为100 typedef struct {int i,j; //非零元的行下标和列下标 ElemType e; //非零元 }Triple; typedef struct {Triple data[MAXSIZE+1]; //...