随笔 - 89  文章 - 118  trackbacks - 0
<2007年12月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

留言簿(16)

随笔分类(56)

随笔档案(89)

文章分类

推荐博客

搜索

  •  

最新随笔

最新评论

阅读排行榜

一年半之前,我遇到一个问题:把一堆数平均分成N份,保证每一份的和接近于所有数之和除以N,不要求平分以后的每份数据个数相等。这是有现实的程序设计需求的,当时是3份。首先想到要先进行排序,再依次从已排序的数列中抽取,如何进行抽取方法有很多,我大概想了3种左右,感觉要拿一些数据去测试一下这几种方法哪一种可以逼近最优解。

当时经理要求算法一定能够得出最优解,但测试多组数据,没有发现哪一种实现能得到最优解。后来翻了一下数据结构、算法与应用--C++语言描述,忽然想到,原来这个是一个典型贪婪算法问题,这个问题没有最优解,用贪婪算法来解决这个问题可以让每一次结果逼近最优。实现如下(注:代码是我今天写的):

typedef vector<int>       IntVector;
typedef vector
<IntVector> IntMat;

void DeuceNumber(const IntVector &SourceVecNum,
                 const 
int       nShare,
                 IntMat          
&OutVecVecNum)
{
    IntVector copySourceNum 
= SourceVecNum;
    sort(copySourceNum.begin(), copySourceNum.end(), greater
<int>());

    IntVector sum(nShare);
    OutVecVecNum.resize(nShare);

    
for (int i = 0; i < copySourceNum.size(); i++)
    {
        const 
int nMinSumPos     = min_element(sum.begin(), sum.end()) - sum.begin();
        OutVecVecNum[nMinSumPos].push_back(copySourceNum[i]);
        sum         [nMinSumPos] 
+= copySourceNum[i];
    }
}

我上传了一个VC的测试工程,有兴趣的朋友点此下载

理论的依据不仅指导了实践的选择,同时给选择以有力的支撑。

2007年就要结束了,在此预祝大家在新的一年里:身体健康,平安如意!
posted on 2007-12-29 15:52 胡满超 阅读(4026) 评论(12)  编辑 收藏 引用

FeedBack:
# re: 怎么样把一堆数平均分成N份 2007-12-29 16:45 winsty
这个不是最优解吧
只能是近似优  回复  更多评论
  
# re: 怎么样把一堆数平均分成N份 2007-12-29 17:16 BlackDream
楼主的程序无法保证平分!
  回复  更多评论
  
# re: 怎么样把一堆数平均分成N份 2007-12-29 17:53 胡满超
@winsty
我认为这个问题没有最优解,贪婪算法从理论上解释了此种方法逼近最优。  回复  更多评论
  
# re: 怎么样把一堆数平均分成N份 2007-12-29 18:00 胡满超
@BlackDream
的确,平分的提法容易使人理解出多种含义。这里是指,分配后的N组数,每组之和接近所有数之和除以N,并且只考虑和不考虑每组数的个数。

这里面有一个数学的问题,就是如何衡量最优解?
我认为是:

((第1组数和-总和/N)+(第2组数和-总和/N)+...)/N

这个值越小结果越优。  回复  更多评论
  
# re: 怎么样把一堆数平均分成N份[未登录] 2007-12-29 19:06 jarod
把一个数组平均分成和相等的两份,这是一个NPC问题,分成N份,N>=3时,更是NPC问题.  回复  更多评论
  
# re: 怎么样把一堆数平均分成N份 2007-12-29 21:15 winsty
把一个数组平均分成和相等的两份,这是一个NPC问题

????
不是吧... 有确定算法的吧
zoj上就有道类似题

N>=3 就不清楚了  回复  更多评论
  
# re: 怎么样把一堆数平均分成N份 2007-12-29 21:32 空明流转
建议用最小二乘作为指标。  回复  更多评论
  
# re: 怎么样把一堆数平均分成N份 2007-12-29 21:33 abettor.org
附件里是啥东西啊?满不相关啊!  回复  更多评论
  
# re: 怎么样把一堆数平均分成N份 2007-12-29 22:56 胡满超
@abettor.org
太抱歉了,本人疏忽链接没有弄对。已经更正了。  回复  更多评论
  
# re: 怎么样把一堆数平均分成N份[未登录] 2010-09-01 22:24 snow
能问您一个麻烦点的问题么
我没有看懂这个算法,你能稍微说一下DeuceNumber函数的主要思想吗?因为我要用c#实现这个,万分感谢!  回复  更多评论
  
# re: 怎么样把一堆数平均分成N份 2010-09-03 08:47 胡满超
主要思想就是贪婪算法,依次遍历N个数,然后分别把它们放入三个数组(数字筒)里,三个数组哪个和最小,就把当前数放到哪个数组里,放入以后三个数组的和大小顺序会发生变化,程序下一次需要重新计算一下哪个数组最小@snow
  回复  更多评论
  
# re: 怎么样把一堆数平均分成N份 2010-09-03 08:50 胡满超
这个问题的确NP完全问题,在《编程之美》里有更加完美的答案,请大家查阅。标准的解放算法复杂度比较高。@jarod
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理