【oj每周推荐】找出最小值
输入：输入一组正整数（可重复），用空格隔开
输出：把输入的整数分成两组，将这两组数的和相减，得出的最小值即为结果
样例：输入：5 13 27 8 14 输出：3
可以这样分：第一组5+27=32 第二组：8+13+14=35,35-32=3
也可以这样分：第一组8+27=35 第二组：5+13+14=32 ，35-32=3
不管怎样分，求出这个最小值即可

[解决办法]
先退化：
如：8 8 9 9 3 3 1 3 4 5 6
退化成1 3 4 5 6
之后，再行比较这个数据的极小值

退化完成之后的算法示例：

C# code

public int FindMin(string OriginalInput){    string[] ArrayInput = OriginalInput.Split(new string[]{" "}, StringSplitOptions.RemoveEmptyEntries);    // TODO:......    // 退化算法开始排除里面成对的重复值.    int SumArr1 = 0, SumArr2 = 0;    foreach(int nextInt in arrResult)    {        // arrResult 是退化后的整数数组         if(SumArr1 > SumArr2)            SumArr2 += nextInt;        else            SumArr1 += nextInt;    }    return Math.Abs(SumArr1 - SumArr2);}
[解决办法]
补充：退化算法可以分两步，也可以一步做完
两步：
1.先使用经典的排序算法，将数组排序
2.按顺序遍历数组，当n与n+1相等时，则剔除，当然，这里步长为 +2，只做奇数或偶数的遍历，数据多的时候时间可以省下不少.
一步：
1. 如果使用冒泡这种排序方法.则，在排序的时候，即可剔除相同的两个数据. 需要两个临时变量，一个存放当前值，一个存放上一个值(上一个值一定是没有重复的)

退化完毕之后，可以使用上述方法来操作数据进行相关的求差.

_________________________________________________________

先抛砖，其他兄弟尽管砸~
[解决办法]
探讨

需不需要先排序输入的数字,然后从大往小了加 

[解决办法]
探讨

先退化：  
如：8 8 9 9 3 3 1 3 4 5 6  
退化成1 3 4 5 6  

   // 退化算法开始排除里面成对的重复值.

[解决办法]
这是我用动态规划解决该问题的代码
程序的输入输出有待优化，先贴出来给大家看下，优化后再发一份


public class Acm1005  
{
Acm1005(){}
   public void Kitbag(){}
public int KnapSack(int v[],int w[],int c,int n,int m[][])
{
/*****初始化********/
int jMax=min(w[n]-1,c);//
for (int j=0;j<=jMax;j++)/*m(n,j)=0   0=<j<w[n]*/
{m[n][j]=0;}//在m矩阵最后一行，比jmax小的单位放不下
for (int j=w[n];j<=c;j++)/*m(n,j)=v[n]   j>=w[n]*/
{m[n][j]=v[n];}//比jmax大的单位能将第n个物品放下

/*****将剩下的n-1个物品放进去*****/
for (int i=n-1;i>1;i--)
{ 
jMax=min(w[i]-1,c);//选择第i个物品
for (int j=0;j<=jMax;j++)/*m(i,j)=m(i+1,j)   0=<j<w[i]*/
{m[i][j]=m[i+1][j];}//在放不进第i个物品的位置保留，记录原来的情况
for (int j=w[i];j<=c;j++)/*m(n,j)=v[n]   j>=w[n]*/
{m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}
//在能放进第i个物品的位置，有选择性的确定是替换还是不替换，并记录
m[1][c]=m[2][c];
if(c>=w[1])
{m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}
}
for(int i=1;i<6;i++)
{
for(int j=0;j<11;j++)
{
System.out.print(m[i][j]+" ");
}
System.out.print("\n");
}

int j=0;
return m[1][10];
}
public int max(int a,int b)
{
if(a>=b){return a;}
else{return b;}

}
public int min(int a,int b)
{
if(a>=b){return b;}
else{return a;}
}
public static void main(String[] args)
{
Acm1005 acm1005=new Acm1005();  
int[] w={0,2,2,6,5,4};// 石头的重量，由于个人习惯，数组的0位置不放
int[] v={0,2,2,6,5,4};//每一个石头的值为1
int halfWeight=10;
int[][] m=new int[6][halfWeight+1];
//m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值
System.out.print("最小值为："+(19-2*acm1005.KnapSack(v,w,10,5,m)));

}

}
[解决办法]
程序如下：

用.net 3.5编写，大量用到LINQ，楼主用.net 3.5创建一个C# Console Application Project，然后将我的程序Copy + Peste即可

给分

using System; 
 
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
   class Program
   {
       static void Main(string[] args)
       {
           WordsMagic wm = new WordsMagic(new int[] { 5,13,27,8,14,78,12,86 });
           wm.Split();
           wm.Calculate();
           wm.Filter();
           wm.OutPutResult();
       }
   }

   public class WordsMagic
   {       
       public int[] RawArrays
       {
           get;
           set;
       }

       private List<KeyValuePair<int, int>[]> tmpResult = null;
       private List<KeyValuePair<int, int>[]> finalResult = null;
       int theMin = 0;

       public WordsMagic(int[] rawArrays)
       {
           RawArrays = rawArrays;
       }

       public void Split()
       {
           var tmpKV = RawArrays.Select((s, n) => new KeyValuePair<int, int>(n, s)).ToArray();
           tmpResult = new List<KeyValuePair<int, int>[]>();
           int loopNum = RawArrays.Length / 2;

           for (int i = 2; i <= loopNum ; i++)
           {
               KeyValuePair<int, int>[] tb = new KeyValuePair<int, int>[i];
               GetNumbers(i, tmpKV, tb);
           }
       }

       public void Calculate()
       {
           var tmpKV = RawArrays.Select((s, n) => new KeyValuePair<int, int>(n, s)).ToArray();

           theMin = tmpResult.Min(fstPart =>
               {
                   var indexArray = fstPart.Select(s => s.Key);
                   var sndPart = tmpKV.Where(s => !indexArray.Contains(s.Key));
                   return Math.Abs(fstPart.Sum(s => s.Value) - sndPart.Sum(s => s.Value));
               });

           finalResult = tmpResult.Where(fstPart =>
               {
                   var indexArray = fstPart.Select(s => s.Key);
                   var sndPart = tmpKV.Where(s => !indexArray.Contains(s.Key));
                   return Math.Abs(fstPart.Sum(s => s.Value) - sndPart.Sum(s => s.Value)) == theMin;
               }).ToList();
       }

       public void Filter()
       {
           var gResult = finalResult.GroupBy(fstPart =>
               {
                   string tmpString = "";
                   foreach (var item in fstPart.OrderBy(item => item.Value).Select(item => item.Value))
                   {
                       tmpString += item + ",";
                   }
                   tmpString = tmpString.TrimEnd(',');
                   return tmpString;
               });
           finalResult = gResult.Select(s => s.First()).ToList();
       }

       public void OutPutResult()
       {           
           var tmpKV = RawArrays.Select((s, n) => new KeyValuePair<int, int>(n, s)).ToArray();

           foreach (var fstPart in finalResult)
           {
               string fstStrings = "";
               foreach (var item in fstPart)
               {
                   fstStrings += item.Value.ToString() + "+";
               }
               fstStrings = fstStrings.TrimEnd('+');

               string sndStrings = "";
               foreach (var item in tmpKV.Where(x => !fstPart.Select(s => s.Key).Contains(x.Key)))
               {
                   sndStrings += item.Value.ToString() + "+";
               }
               sndStrings = sndStrings.TrimEnd('+');
               Console.WriteLine("ABS[(" + fstStrings + ") - (" + sndStrings + ")] = " + theMin.ToString());
           } 
 
       }

       public void GetNumbers(int num, KeyValuePair<int, int>[] subNum, KeyValuePair<int, int>[] tmpBuffer)
       {
           var mTmpBuffer = tmpBuffer.ToArray();
           if (num > 0)
           {               
               for (int i = 0; i < subNum.Length; i++)
               {
                   mTmpBuffer[num - 1] = subNum[i];
                   var tmpSubNum = subNum.Where((s, n) => n != i).ToArray();
                   GetNumbers(num - 1, tmpSubNum, mTmpBuffer);
               }

               return;
           }
           tmpResult.Add(mTmpBuffer);
       }
   }
}

[解决办法]
应该先计算总和，取为sum ，然后利用快排排序，排好序列后，然后前一半求和sum1，设试探性函数abs（sum-2sum1），向中间位置数的前一项和后一项运动，观察abs的趋势，想减小方向运动，直至abs再次增大。前一项abs即为最小值。

关于为什么计算sum-2sum1
设剩下的为sum2 =sum-sum1
原问题转成abs（sum1-sum2）=abs（2sum1-sum）。
代码有时间贴上，要上课了
[解决办法]
遍历 将数组中最接近的2个数运算 这样 新数组就是原数组的n/2
循环
直到新数组只有一个

不知道这样可以不？
[解决办法]
我认为这个是就个排序

比如说 1 2 3 4 5 6
你会怎么把这组数分成平均的两组
会先在数中间切开 123 | 456
最大和最小放一组,次大的和次小的放一组
1 6 3
2 5 4 
就这个样子
[解决办法]
都是整数的话,其实就是用状态压缩的动态规划解一个大小为sum/2的01背包。其中sum 是所有数的加和。

前段时间的一个帖子，C和C#的思路稍有不同
http://topic.csdn.net/u/20090511/23/a482be66-6598-46fa-be19-e7e356e2244b.html
[解决办法]
我是这样想的
1、首先排序
2、然后分成两组，分组规则：
一组从大的开始加逼近和的一半，二组留下最小值（一组的数量<2,结束）
3、调整两边的重量，使其差逐步减小，调整目标：差值小于等于最小值。
算法的特点是：一直保持最小值在一端不动、调整的目标是差值小于最小值

重量调整的时候需考虑的比较多，有1换多，n换m的情况。
[解决办法]
探讨

要两组数字和的差最小，即一组数字和与 总和/2 最接近，问题就变成“找出一组数字和 与 指定数值最接近”，是不是比原来的题目好解一些

[解决办法]
弱弱的发我的第一次回帖
先排序，像高斯算数那样，比如从大到小排序，然后1，3，5，7大放一组，然后2，4，6，8大放一组
分组后
小组内再排序
1+7与3+5的差应该是第一组中最小的
2+8与4+6的差应该是第二组中最小的


我觉得我这种想法还是得去论证- -

[解决办法]
我的想法是：从叶节点向跟创建一个二叉树的过程。具体如下：
先把每个输入的数值都当作一个叶子，排序，第一大和第二大一组，求差作为它们的父节点；第三大和第四大一组，求差作为他们的父加点，以此类推，然后再把所有的父节点的值排序，再分组求差，直到求出根节点，就是最中值了。根节点的两个子节点下的叶子，就是分组了。
请高手指教。