[开_93] 来试试离散排列组合的最优算法

okkey

有任意大于零的N个数（A1，A2，A3，......，AN），设N个数之和为S，试编写这样一个程序：假设把这N个数分为M组(C1，C2，C3，......CM），V=S/M，使得这M组数的每组数之和（每组数之和表示为SC1，SC2，SC3，......，SCM）与V值的总离散值D是最小的，而且程序可以将这M组数排列好，请下载附件的例子。附件的XLS文件中是将任意17个数分成3组数，在A列中有17个数，请编写上面要求的程序，并输出如XLS文件中的结果。这里的总离散值可定义为D=|V-SC1|+|V-SC2|+......+|V-SCM| OM4owxVy.rar (1.91 KB, 下载次数: 35)

2006-3-13 20:43 上传

点击文件名下载附件
来试试离散排列组合的最优算法

[此贴子已经被apolloh于2006-3-21 8:39:26编辑过]

sandyw

唉，离散数学。晕。偶没学过，总离散值是什么都不知道。

northwolves

用了将近5分钟才找出,不好意思贴出代码来了

northwolves

按你的总离散值的定义,存在最小总离散值为0的组合,我是穷举出来的,总计算时间4.9分钟.

northwolves

Sub xxxxx()
Dim x As String, t As Long, k As Long
x = "0047FFD00519C30054D05006E7150071A57007B41D04247E10427B2304314E904415330444875044AEF9045157D0457C01045AF43046AF8D04749530477C95052E3630537D29053B06B054B0B5055E4410564AC505717CD0574B0F057B19305818170587E9B058B1DD0631B45063B50B063E84D064E8970661C2306682A70674FAF06782F1067E9750684FF9068B67D068E9BF06B2CEC06BC6B206BF9F406CFA3E06E2DCA06E944E06F615606F949806FFB1C07061A0070C824070FB6607352FD073ECC30742005075204F07653DB076BA5F0778767077BAA9078212D07887B1078EE3507921770838ADF08424A508457E708558310868BBD086F241087BF49087F28B088590F088BF93089261708959590E4DA550E5741B0E5A75D0E6A7A70E7DB330E841B70E90EBF0E942010E9A8850EA0F090EA758D0EAA8CF0F512370F5ABFD0F5DF3F0F6DF890F813150F879990F946A10F979E30F9E0670FA46EB0FAAD6F0FAE0B10FD23DE0FDBDA40FDF0E60FEF13010024BC1008B4010158481018B8A101F20E1025892102BF16102F25810549EF105E3B510616F710717411084ACD108B1511097E59109B19B10A181F10A7EA310AE52710B186911581D11161B971164ED91174F2311882AF118E933119B63B119E97"
x = x & "D11A500111AB68511B1D0911B504B17243241741076174AA3C174DD7E1759D97175D0D9176375D1769DE1177046517737A717804AF1786B331799EBF17A54E917A9F0917AD24B17B6C1117C223B17CBC0117CEF43185D57918608BB1866F3F186D5C31873C471876F891883C91188A315189D6A118A8CCB18AD6EB18B0A2D18BA3F318C5A1D18CF3E318D2725192B2DC194802E19519F41954D362043A162060768206A12E206D4702079489207C7CB2082E4F20894D3208FB572092E99209FBA120A622520B95B120C4BDB20C95FB20CC93D20D630320E192D20EB2F320EE635217CC6B217FFAD2186631218CCB52193339219667B21A338321A9A0721BCD9321C83BD21CCDDD21D011F21D9AE521E510F21EEAD521F1E17224A9CE226772022710E622744282506C3825105FE2513940252D3502530692253A05825892492592C0F2595F5125AF96125B2CA325BC669260A41A2613DE026171222630B322633E74263D83A279020D2799BD3279CF1527B692527B9C6727C362D"
Range("h3:j19").ClearContents
Randomize
t = CLng(InputBox("洒家找到242种不同组合,请输入您想显示第几个?", "提示", Int(242 * Rnd) + 1))
t = CLng("&H" & Mid(x, t * 7 + 1, 7))
Cells(3, 8) = Cells(3, 2)
For k = 4 To 19
Cells(k, 8 + t Mod 3) = Cells(k, 2)
t = t \ 3
Next
End Sub

northwolves

还是献丑吧,计算时间太长,不知如何优化

4ADoIt3j.rar (12.69 KB, 下载次数: 48)

2006-3-14 12:34 上传

点击文件名下载附件
来试试离散排列组合的最优算法

lee1892

我的直觉，分组使得每组数之和越接近越好，貌似灰袍那个分班的代码可以借鉴，虽然我还没看过他的代码～