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

  • 主题发起人 主题发起人 way2
  • 开始时间 开始时间
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1016791
 
这不是背包算法吗？你去找找数据结构里头的背包算法例程看看就搞定了。
 
to lldhz:
哈,我你是没看懂我写的算法呢!
接近就是最接近,更本无法事先知道比w/2小多少,但最多等于[W+1/2],
必须用穷举加约束条件(也就是回溯法).
实际上我的算法是对穷举法加上一个条件(实际上也是回溯法),使小于<W/N,
因为每次都重新算一遍注意,每次的Wi不同!Wi就是每减小一个规模后的总和!
所以根本不存在你讲的:
"其中有N组非常接近平均值，但后面的几组有可能和平均值相差很大"
情况!
另外,"排序算法都效率是不用考虑的，我是检最熟悉的用！效率低？你老兄把你的实现看看！"
笑话,假如你连快速排序法都不会,那我以后就不会和你讨论了!
 
还有"是每个累加和与它们平均数的差的绝对值的和最小"
这都不会?
就是设置一个变量,保存当前的绝对值和最小的值(初始化为最大整数),
如果这次查找的组合算出来的绝对值和比那个变量小就把它赋为当前值!
如果你真的连这一点都不会,那我就没有必要留在大富翁论坛了!
 
我没有细看前面的贴子，排序后两头取是一个不错的思路。
但我觉得应该把"使每份的累加和尽量接近或相等"进行量化或公式化。
比如，最大和与最小和的差最小。
 
>>排序算法都效率是不用考虑的，我是检最熟悉的用！
在这个问题中是可以不要考虑排序的效率，做一次排序就行。在你的算法中也忽略了！
快速排序不是不会，但是从大2考到大4都是考冒泡法，没办法，想不是最熟悉都不行！
呵呵，是没看懂！：）
现在懂了！
其实你的算法是：现在找出最接近的，然后在剩余的里面找最接近剩余的数和的平均值的组；
这样是可以了！谢谢！看来想投机还还是不行啊！
呵呵，刚出来，经验不足，也太冲动了！希望不要介意！[:P]
交个朋友！我的QQ是30196426！
 
排序虽然只有一次,但花的时间可不少.
冒泡法的复杂度达到O(n^2)而快速排序法只有O(n*log2(n));
如果碰到糟糕的情况排序花的时间有可能比查找的时间还要长,所以不能忽略.
你还是没有弄明白我的意思,我是加了一个约束的穷举,而穷举的办法是递归,
递归到n=2的时候就可以利用算法书上的一个常见算法:"求若干个数的和接近一个指定的数"
你的思路是用一个大的加到一个小和的办法,这实际上是贪心算法,它需要的时间很少;
但只能求到较优解,无法求到最优解.
 
>>先找<w/n的一组，再找<wi/(n-1)的一组最后到n=2的情况
和我理解的‘先找出最接近的，然后在剩余的里面找最接近剩余的数和的平均值的组’
好象是一样啊！
可能是我的表达有错吧！
我的意思是：先求出最接近W/N；然后去掉已分组的数，剩余再接近的wi/(n-1)的……
我觉得是递归调用求若干个数的和接近一个指定的数的算法！
写程序好久没考虑过复杂度了，都是在COPY了（用delphi)，现在自己写个公式解析器
都是困难，真是对不住老师啊！
 
好热闹，我想想先
 
关于这个算法，我编了一段代码，当然，既然原来的要求是分成
2份，我就简单点，作了分成两份的算法。
算法的基本原理是这样的：
1：算出所有数的总和，以及平分的理想数（当然就是除以2了）
2：用数组把数据分成两份，不必排序，只要平分就行。第一组为目标数，第二组是剩下数。
3：计算出目标数组中的总和，得到目标数的总和和理想数的差值
4：用2重循环，找第一组目标数和第二组剩下数中的两两之间的差值。
5：如果差值等于小于 理想数－目标数的总和 的差值，置换这两个数，结束2重循环
6：如果对第一组目标数和第二组剩下数做过置换,重复3
7：如果没有做过置换，结束计算
以下是代码(注意，数组中必须是偶数个，否则需要改一下代码）
var a: array[0..9] of integer = (11,32,43,12,115,19,37,28,119,105);
procedure TForm1.Button1Click(Sender: TObject);
var i,j,n,sum: integer;
target:do
uble;
targetA,OtherA: array of integer;
tempTarget: integer;
SubValue:do
uble;
CloseValue,tempSub:do
uble;
tempValue: integer;
Replaced: Boolean;
begin
sum := 0;
for i := low(a) to high(a)do
sum := sum + a;
target := sum / 2;
n := Length(a) div 2;
SetLength(TargetA,n);
SetLength(OtherA,n);
for i := 0 to n - 1do
begin
TargetA := a;
OtherA := a[i+n];
end;
while truedo
begin
tempTarget := 0;
for i := 0 to n - 1do
begin
tempTarget := tempTarget + TargetA;
end;
SubValue := Target - tempTarget;
CloseValue := SubValue;
Replaced := false;
for i := 0 to n - 1do
begin
for j := 0 to n - 1do
begin
tempSub := OtherA[j] - TargetA;
if (tempSub < 0) and (CloseValue < 0) then
begin
tempSub := -tempSub;
CloseValue := -CloseValue;
end;
if (abs(CloseValue - tempSub) < CloseValue) and (tempSub >= 0) then
begin
CloseValue := tempValue;
tempValue := TargetA;
TargetA := OtherA[j];
OtherA[j] := tempValue;
Replaced := true;
break;
end;
end;
if Replaced then
break;
end;
if not Replaced then
break;
end;
Edit3.Text := '';
Edit4.Text := '';
tempTarget := 0;
for i := 0 to n - 1do
begin
Edit3.Text := Edit3.Text + IntToStr(TargetA) + '+';
Edit4.Text := Edit4.Text + IntToStr(OtherA) + '+';
tempTarget := tempTarget + TargetA;
end;
Edit5.Text := IntToStr(tempTarget);
Edit6.Text := IntToStr(sum-tempTarget);
Edit1.Text := IntToStr(sum);
Edit2.Text := FloatToStr(Target);
end;

原始随机数 11,32,43,12,115,19,37,28,119,105
结果
第一组 37+32+43+28+119 和为 259
第二组 11+12+19+115+105 和为 262
 
效率一般,比较苯,如果不要求速度,应该还可以用,呵呵。我自始至终没用排序,不知用排序
会不会提高效率。可是我不知道排序怎么才能用在我这个算法里面 :(
 
我的算法肯定能找到最优解（也就是说，肯定是正确的），只是算法的效率大家可能不满意
如果需要分成N份，修改代码是很容易的，也就是第一次分的时候，不是平分，而是分成第一
组目标数组（M／N个数）和 第二组是剩下数，再来个递归就可以。如果大家觉得我的算法能
用，还想在这个算法下研究以下N组分法，我就再把N组分法实现了
 
楼上：不行！
你把你的11改成15试试！得的结果不是最优的！
(就是你原来的数据也不是最优解11+19和28互换才是。）
你的代码就测试了一组数据？？把指定数组改成随机产生更具普遍性吧！
 
改正了一点判断的小错误,望lldhz见谅,您再看看
 
>>(就是你原来的数据也不是最优解11+19和28互换才是。）
那数组的个数就不对了，我理解数据的个数是要平分的，不知理解是否正确？
 
哦！你是这样理解的啊？？你搞错了，现在求的是均分和（不要一定均分个数）
 
>>把不定量的一组随机数平分成n份使每份的累加和尽量接近或相等,请高手指教。
~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~
原来的提问是这样的,是我理解错了?我糊涂了!
 
>>原始问题只不过要求简单一些，只分成两份。但如果能分成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 这样是最佳方案，
>>也就是说两组数之差最小
搞不清均分还是不是均分,唉,我的理解有点问题,唉,人老了
 
哈哈！
反正各有各的理解吧！
还是楼主来解释一下吧！
 
如果不是均分,下面的代码不知行不行?
var a: array[0..9] of integer = (11,32,43,12,115,19,37,28,119,105);
procedure TForm1.Button1Click(Sender: TObject);
var i,j,len1,len2,sum: integer;
target:do
uble;
targetA,OtherA: array of integer;
tempTarget: integer;
SubValue:do
uble;
CloseValue,tempSub:do
uble;
tempValue: integer;
Replaced: Boolean;
begin
sum := 0;
for i := low(a) to high(a)do
sum := sum + a;
target := sum / 2;
len1 := Length(a);
len2 := Length(a);;
SetLength(TargetA,len1);
SetLength(OtherA,len2);
for i := 0 to len1 - 1do
TargetA := a;
for i := 0 to len2 - 1do
OtherA := 0;
while truedo
begin
tempTarget := 0;
for i := 0 to len1 - 1do
begin
tempTarget := tempTarget + TargetA;
end;
SubValue := Target - tempTarget;
CloseValue := SubValue;
Replaced := false;
for i := 0 to len1 - 1do
begin
for j := 0 to len2 - 1do
begin
tempSub := OtherA[j] - TargetA;
if (tempSub < 0) and (CloseValue < 0) then
begin
tempSub := -tempSub;
CloseValue := -CloseValue;
end;
if (abs(CloseValue - tempSub) < CloseValue) and (tempSub >= 0) then
begin
CloseValue := tempValue;
tempValue := TargetA;
TargetA := OtherA[j];
OtherA[j] := tempValue;
Replaced := true;
break;
end;
end;
if Replaced then
break;
end;
if not Replaced then
break;
end;
Edit3.Text := '';
Edit4.Text := '';
tempTarget := 0;
for i := 0 to len1 - 1do
begin
Edit3.Text := Edit3.Text + IntToStr(TargetA) + '+';
tempTarget := tempTarget + TargetA;
end;
for i := 0 to len2 - 1do
Edit4.Text := Edit4.Text + IntToStr(OtherA) + '+';
Edit5.Text := IntToStr(tempTarget);
Edit6.Text := IntToStr(sum-tempTarget);
Edit1.Text := IntToStr(sum);
Edit2.Text := FloatToStr(Target);
end;
 
您必须登录或注册才可回复。

Similar threads

S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
3K
SUNSTONE的Delphi笔记
S
S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
2K
SUNSTONE的Delphi笔记
S
D
[原]希望OrangeUI有个好的开始
回复
0
查看
1K
DelphiTeacher的专栏
D
I
常用算法（2）分而治之算法
回复
0
查看
734
import
I
D
[原]OrangeUI－Delphi移动开发利器
回复
0
查看
2K
DelphiTeacher的专栏
D
后退
顶部