【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
之后，再行比较这个数据的极小值
退化完成之后的算法示例：
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. 如果使用冒泡这种排序方法.则，在排序的时候，即可剔除相同的两个数据. 需要两个临时变量，一个存放当前值，一个存放上一个值(上一个值一定是没有重复的)
退化完毕之后，可以使用上述方法来操作数据进行相关的求差.
_________________________________________________________
先抛砖，其他兄弟尽管砸~
[解决办法]
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的情况。
[解决办法]