寻求一个均分算法 (如能解决高分奉送) (100分)

W

way2

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-01

• #1

把不定量的一组随机数分成n份使每份的累加和尽量接近或相等,请高手指教。

 

P

pckite

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-01

• #2

我也在想这个问题。

 

H

hlsl

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-01

• #3

分后的顺序没有要求吗？
如果没有顺序要求，有一个简单的做法，就是先排序，然后首末取出分组
复杂一点的做法，就是搜索了吧？

 

R

renyi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-01

• #4

排序的想法可以，就如楼上所言，首尾取分组数

 

W

way2

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-02

• #5

一般的想法都想过了，首尾取行不通的。随便举个例子：
1 2 3 4 5 9 10 30 78

 

D

dx_zhang1978

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-02

• #6

1.首先排序An
2.求出平均值q
3.找出最接近平均值q的数A在数列An中的位置i
4.从位置i开始左右两边取分组数

 

光

光子

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-02

• #7

比较笨的方法：
　　第一步：从大到小排序。（78 30 10 9 5 4 3 2 1）
　　第二步：计算分组后的每组和的理论值。（理论和m = 所有数的和s　除以　欲分的组数n）
　　第三步：循环分组（i=1 to n-1）（最后剩余的得一组）
　　　　　　循环体：取第一个数属于本组，
　　　　　　　　　　如果下一个数加入本组后的和：非常靠近m　　则加入此数到本组，并结束本组
　　　　　　　　　　　　　　　　　　　　　　　　比m小得多　　则加入此数到半组，继续分组
　　　　　　　　　　　　　　　　　　　　　　　　比m大得多　　则放弃此数，继续分组
说明，这不是最佳的算法，分组有时候不太合理。

 

W

way2

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-02

• #8

谢谢光子，这种方法以前也想过了，确实有些时候不合理。
特别是当有些数很接近但和其他几个数相差又很远时，就会很不准确。
如:把
100
77
50
20
19
2
1
按那种方法分成两组时就不准确了，数再大些差的会更大，所以放弃了。
我觉得可能要用到一些数理统计算法才能解决了。不知有没有更好的算法可以赐教，谢谢。

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-02

• #9

有难度...

建议将此问题转移到“数据结构”分类。(“编辑”即可)

 

T

Tuatara

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-02

• #10

你不妨把原始问题也贴出来，或许大家可以用另外的思路解决，
就你现在的问题来说，在有些情况下是无解的，而且有时解也不是唯一的，如何评价是否
达到你的要求？你的“最接近”是什么概念？

 

W

way2

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-02

• #11

原始问题只不过要求简单一些，只分成两份。但如果能分成n份更好。
嘴接近，就是要最佳方案喽。比如这组数
100 77 50 20 19 2 1
totoal/2=134.5
I(100+20+2+1)=123 II(77+50+19)=146 这样分就不是最佳方案
I(100+20+19)=139 II(77+50+2+1)=130 这样是最佳方案，
也就是说两组数之差最小

 

T

Tuatara

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-02

• #12

如果不考虑效率的话用数据解决肯定是可以的，但如果考虑效率的话
我觉得用数组可能无法做到，试试用图的方法解决。我觉的这个问题
和“最小生成树”有相似之处。看看是否能给你一点启发。

 

Z

zjczxd

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-05

• #13

我以为:
1.首先要解决累加和怎样才算更接近或更相等?
假设：是每个累加和与它们平均数的差的绝对值的和最小。
2.如果有m个数,n显然必须比它小，否则没有意义。
实际上，必须满足 n<<m 才有实际意义，我就假设这点成立。
假设所有数的总和为 W，数据都是排好了序的。
先从最简单的情况入手：
n=2: 显然，我们只要从中找到若干个数，使它们的和最接近 W/2就可以了；
这很容易用回溯法实现。
n=3: 必须设法找到第一组数；糟糕的是我们必须逐一扫描，获得第一组数，
然后才可以用n=2的办法找出一个方案，记录三个数绝对值差的和进行比较，得到最优解。
实际上，分成的三组必然有一组小于W/3,所以在穷举第一组数时，可以认为第一组必然
小于W/3。按照这个办法进行回溯可以大大加快效率。
显然这个办法可以从3推广到任意值。先找<w/n的一组，再找<wi/(n-1)的一组最后到n=2的情况。
这是我的鄙见，还望高手不吝赐教。

 

L

lldhz

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-03

• #14

我好象找到一个可行的简单方法，没测试；各位可以试试：
分N组，各组的和记z[1]...z[n]：
1.按从大到小排序，记a[1].....a[m];
2.按从大到小把前N个数分别放到1.....n组;
3.把a中剩余的最大的分给z中最小的组；
4.z=z+a[j]然后z[1].....z[n]排序；
5.循环3，到a结束

 

B

barton

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-03

• #15

呵呵，我来谈谈。
1.先求和S，每份最佳值是X=S/n；
2.开始随机取数，每取一个数作一个标记,直到该份的总和接近X,得到一份；
^^^^
3.重复第2步,直至所有数全部被取光.
排序就会带有一定的规律性,每份数据就不会很平衡.这样不好.

 

Z

zjczxd

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-03

• #16

郁闷,找了无数论坛, 它们都有一个特点:高手的数量太少!

 

L

lldhz

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-04

• #17

我的方法在大多情况下是最优解，但是在有可能出现最大的一组和最小的一组可以微调的
情况（测试了几十组，大概有4-5组）！各位有更好的算法嘛？
PS:测试时发现有多个数非常接近时会出现问题
失败！失败！不行！昨天没注意看，原来得到的结果只是很接近于最优的！
把代码贴出来！看看大家有什么优化的办法没有！

 

L

lldhz

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-04

• #18

#include "stdafx.h"
#include <vector>
#include <valarray>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAX_COUNT = 100;
vector<int> result[MAX_COUNT];
void sort(int *pData, int len)/*排序*/
{
for(int i=0;
i<len-1;
i++)
for(int j=i+1;
j<len;
j++)
if(pData < pData[j])
{
int tmp = pData;
pData = pData[j];
pData[j] = tmp;
}
}
int sumVal;
void sum(int val)/*求和*/
{
sumVal += val;
}
int find_min_col(vector<int> *pArr, int n)/*找最小的行*/
{
sumVal = 0;
for_each(pArr[0].begin
(), pArr[0].end(), sum);
int ret = 0, oldVal = sumVal;

for(int i=1;
i<n;
i++)
{
sumVal = 0;
for_each(pArr.begin
(), pArr.end(), sum);
if(sumVal < oldVal)
{
ret = i;
oldVal = sumVal;
}
}
return ret;
}
void dispatch(int *pData, int len, int n)/*分组*/
{
sort(pData, len);

for(int i = 0;
i < len;
i++)
{
int index = find_min_col(result, n);
result[index].push_back(pData);
}
}
void disp(int val)
{
cout << val << ' ';
}
#include <time.h>
int main(int argc, char* argv[])
{
int data[10];
srand(time(NULL));
for(int i = 0;
i < 10;
i++)/*控制数的多少，取数*/
{
data = rand() % 100;
}
dispatch(data, 10, 3);
int allsum = 0;
for(i=0;
i<3;
i++)
{
sumVal = 0;
for_each(result.begin
(), result.end(), sum);

allsum += sumVal;
cout << "/n" << sumVal << " ";
for_each(result.begin
(), result.end(), disp);
}
cout << endl << allsum / 3 << endl;

return 0;
}
vc++6.0下写的

 

Z

zjczxd

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-04

• #19

lldhz: 看老兄的排序法吧，居然是冒泡法！怎么也要快速排序法吧？
另外，你的算法固有的错误不说，就实现你的想法来说这种算法也是效率很低的了！
好象我的算法是随随便便就出来了一样！

 

L

lldhz

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-04

• #20

排序算法都效率是不用考虑的，我是检最熟悉的用！
效率低？你老兄把你的实现看看！
你的算法不是随随便便就出来了
我也没说啊！我只是把我的想法说出来而已！
》》是每个累加和与它们平均数的差的绝对值的和最小
怎么操作啊？？
》》我们只要从中找到若干个数，使它们的和最接近 W/2就可以了
最接近是什么概念？？是差1，2还是0？？
算法并不是给人看，而是要让计算机实现，没办法操作理论上最好又有什么用！
还有按你的算法会其中有N组非常接近平均值，但后面的几组有可能和平均值相差很大！