随机数组，分为两个数组，要求两个数组各自加总的差值最小

随机数组，分成两个数组，要求两个数组各自加总的差值最小
例如这个随机 ROUNDNUM[]{ 17;13;11;10;9;9}
分成两组数组A + B，要求两组数据的各自的总和相差最小（Sum(A数组) - Sum(B数组)差值最小）  

A 数组 和 B数组的长度可以不相等

思路是什么啊？   求解惑....

[解决办法]
要“最小”，只能遍历所有可能，并且取最小的。稍微改进的算法是用动态规划。
如果是“尽可能小”，也就是找近似最优解，那么算法就很多了，很多启发式算法都可以做，比如模拟退火，遗传算法，蚁群算法、神经元网络。
[解决办法]
呵呵,忽然觉得循环那里写得好蠢.另外补上注释.
int[] ROUNDNUM = new int[6] { 17, 13, 11, 10, 9, 9 };//随机数
            Array.Sort(ROUNDNUM);//排序（由小到大）
            int sumA=0;//数组A的和
            int sumB=0;//数组B的和
            int n = ROUNDNUM.Length;//随机数数组长度
            int[] arrayA = new int[n];//A组数组（按照最长的可能长度初始化）
            int[] arrayB = new int[n];//B组数组（按照最长的可能长度初始化）
            int arrayAN = 0;//记录A组的下标
            int arrayBN = 0;//记录B组的下标
            for (int i = n-1; i >=0; i--)//倒序循环，从大向小决策
            {
                int v = ROUNDNUM[i];//当前值
                if (Math.Abs(sumA + v - sumB) > Math.Abs(sumB + v - sumA))//分组决策
                {
                    sumB = sumB + v;//加入B组累计值
                    arrayB[arrayBN] = v;//向B组添加数据
                    arrayBN++;//更新B组下标
                }
                else
                {
                    sumA = sumA + v;//加入A组累计值
                    arrayA[arrayAN] = v;//向A组添加数据
                    arrayAN++;//更新A组下标
                }
            }
            Array.Resize(ref arrayA, arrayAN);//根据下标去掉没有用到的元素
            Array.Resize(ref arrayB, arrayBN);  
            MessageBox.Show((sumA - sumB).ToString());
[解决办法]

引用:

Quote: 引用:

呵呵,忽然觉得循环那里写得好蠢.另外补上注释.
int[] ROUNDNUM = new int[6] { 17, 13, 11, 10, 9, 9 };//随机数
            Array.Sort(ROUNDNUM);//排序（由小到大）
            int sumA=0;//数组A的和
            int sumB=0;//数组B的和
            int n = ROUNDNUM.Length;//随机数数组长度
            int[] arrayA = new int[n];//A组数组（按照最长的可能长度初始化）
            int[] arrayB = new int[n];//B组数组（按照最长的可能长度初始化）
            int arrayAN = 0;//记录A组的下标

            int arrayBN = 0;//记录B组的下标
            for (int i = n-1; i >=0; i--)//倒序循环，从大向小决策
            {
                int v = ROUNDNUM[i];//当前值
                if (Math.Abs(sumA + v - sumB) > Math.Abs(sumB + v - sumA))//分组决策
                {
                    sumB = sumB + v;//加入B组累计值
                    arrayB[arrayBN] = v;//向B组添加数据
                    arrayBN++;//更新B组下标
                }
                else
                {
                    sumA = sumA + v;//加入A组累计值
                    arrayA[arrayAN] = v;//向A组添加数据
                    arrayAN++;//更新A组下标
                }
            }
            Array.Resize(ref arrayA, arrayAN);//根据下标去掉没有用到的元素
            Array.Resize(ref arrayB, arrayBN);  
            MessageBox.Show((sumA - sumB).ToString());

这个算法是不行的， 《 苏小喵 》的说法是正确的，只是写起来会很复杂，计算量太大...

确实.这个算法得到的不是最优解.应该是1
17,9,9
13,11,10 
穷举所有可能性不知道是不是唯一的办法。
我在考虑,能不能在这个算法基础上进行调整,把这个步骤当作前处理。不知道会不会让计算方法简化。
也就是说，上面的算法得到一个相对合理的分组，它的解（3）作为一个评价限值。
优化这个分组的策略有交换元素或者改变从一个组移动到另一个组。
然后又这个3去评价是否值得优化。

当然，这样可能会更糟，呵呵。

查看更多 下一篇