求救一道经典算法问题

henryw

没能力无法建立数学模型啊，如果找到算法应该可以让规划求解做的。但是模型计算量大，如何设计成线性是很重要的。

f_qc

最优方案?

[此贴子已经被作者于2003-10-14 9:46:47编辑过]

f_qc

其实我想最优方案就是限定条件的问题,对于这类方案,最好想的方法就是将所有可能列出,然后去掉不合适的,我的程序如下,你可以试一试,其实就是嵌套循环.但我不明白最优方案的限定,这可能是在实际中的问题?比如,那种方案最节约材料?我可以将程序中加上几个限定条件 Sub qiujie() '求解 Dim m, a1, a2, a3, a4, i, j, k, l, w As Integer m = 2000'总 a1 = 201: a2 = 301: a3 = 401: a4 = 501'切分大小45种方案 w = 0 For i = 1 To 4 Sheet1.Cells(1, i + 1) = "条件" + CStr(i) Next For i = 0 To Int(m / a1)'嵌套循环 For j = 0 To Int(m / a2) For k = 0 To Int(m / a3) For l = 0 To Int(m / a4) If (m - (a1 * i + a2 * j + a3 * k + a4 * l)) > 0 And (m - (a1 * i + a2 * j + a3 * k + a4 * l)) < a1 Then'是否满足条件 w = w + 1 Sheet1.Cells(w + 1, 1) = "方案" + CStr(w) Sheet1.Cells(w + 1, 2) = i Sheet1.Cells(w + 1, 3) = j Sheet1.Cells(w + 1, 4) = k Sheet1.Cells(w + 1, 5) = l End If Next l Next k Next j Next i End Sub

[此贴子已经被作者于2003-10-14 10:00:37编辑过]

wangyuwy

在30楼提供的方法中是将2000分成101，201，301，401时所取的方案的具体例子，实际中即使切分成任何可确定的长度集，结合30楼提供的程序，利用数组提供参数可列出各种方案。35楼的嵌套太原始了，如果需要切100个不同的长度时，需要写100重循环？

f_qc

我想如果用程序实现确实不管对于多少不同方法,都是无法减少计算工作量的,对于100个不同长度,总计算量确实是相当大的.30楼的方法是先将所有的组合列在表中,然后再进行判断,计算量一点也不会少.而且从程序来看,计算量应该是刚好一倍,如果在放置所有可能时直接判断,与嵌套的计算量刚好一样

[此贴子已经被作者于2003-10-14 11:26:20编辑过]

f_qc

我试了一下30楼的程序最大的问题是占用资源过大,你用8000,然后分成6份,你已经无法算了,因为数组越界了.但嵌套循环还是没有问题.还要注意excel的表格行与列不是无限的.如果方案巨大,就不能保存在表格里了.另外,我还是觉得计算量太大,不知还有没有更好的办法?

wangyuwy

就计算梁而言，30楼的算法与35楼算法一样大，它的本质是总结了嵌套循环的数学规律，仿真地实现了多重循环，而不必重写循环。30楼的算法是“N”方向的计算顺序，35楼是“Z”方向的计算顺序。 35楼算法耗费资源大于直接嵌套循环的原因是数组变量比相同元素数的单变量要多耗资源。

henryw

不如让Excel临时在VBA中形成一个程序来作计算。反正写入VBE当中的办法是有的。全部完成后就删掉，用的资源又少，呵呵。

henryw

所以我总是怀疑题目说的或许是，对于101,201,301,401四种都是有规定出产数量的，要满足这些规定出产数量，求2000的料用得最少。太专业的东西简单的描述或许行内人员很容易看懂，可是很难让我们这些外行明白的。

wangyuwy

henryw 理解的完全正确。