求救一道经典算法问题

wanghy750317

goots 发表于 2003-11-5 12:51
我认识的一位朋友，自己用FOXPRO开发了我所提到的两个软件。
但他对源代码特保密！！
我们还是自己动手吧 ...

效果怎么样呢，让他展示给我们看一下吧，无偿的不行，有偿可以得到代码吗！

天晴.Xin

2013年了，问题持续在！

hidaydayup

用lingo和matlab建立数学模型 求解！

香川群子

wangyuwy 发表于 2003-10-14 10:39
在30楼提供的方法中是将2000分成101，201，301，401时所取的方案的具体例子，实际中即使切分成任何可确定的 ...

生成全部整数分割方案的代码：

1. 
   
2. Sub DivNum()
   
3.     Dim a, i&, j&, k&, m&, n&, s$, tms#
   
4.    
   
5.     m = Val(InputBox("整料标准长度：", "整数分割方案", 2000))
   
6.     a = Split(InputBox("各种小料规格,以逗号分割：", "整数分割方案", "101,201,301,401"), ",")
   
7.     tms = Timer
   
8.    
   
9.     n = UBound(a)
   
10.     ReDim b&(n)
    
11.     ReDim c(n + 2, 65535)
    
12.     b(0) = m
    
13.     For i = n To 1 Step -1
    
14.         b(i) = b(0) \ a(i)
    
15.         b(0) = b(0) Mod a(i)
    
16.     Next
    
17.    
    
18.     For j = 1 To 65534
    
19.         If b(0) < a(0) Then
    
20.             s = ""
    
21.         Else
    
22.             s = "+" & a(0) & "*" & b(0) \ a(0)
    
23.             c(0, j) = b(0) \ a(0)
    
24.         End If
    
25.         For i = 1 To n
    
26.             If b(i) > 0 Then
    
27.                 c(i, j) = b(i)
    
28.                 s = s & "+" & a(i) & "*" & b(i)
    
29.             End If
    
30.         Next
    
31.         c(n + 1, j) = "=" & Mid(s, 2)
    
32.         c(n + 2, j) = s
    
33.         
    
34.         For i = 1 To n
    
35.             If b(i) > 0 Then
    
36.                 b(i) = b(i) - 1
    
37.                 b(0) = b(0) + a(i)
    
38.                 For k = i - 1 To 1 Step -1
    
39.                     b(k) = b(0) \ a(k)
    
40.                     b(0) = b(0) Mod a(k)
    
41.                 Next
    
42.                 GoTo Nxt
    
43.             End If
    
44.         Next
    
45.         GoTo Ext
    
46. Nxt:
    
47.     Next
    
48.     MsgBox "Over ! ": Exit Sub
    
49. Ext:
    
50.     MsgBox Format(Timer - tms, "0.000s ") & j
    
51.     For i = 0 To n
    
52.         c(i, 0) = a(i)
    
53.     Next
    
54.     c(n + 1, 0) = m
    
55.     c(n + 2, 0) = j
    
56.    
    
57.     ReDim Preserve c(n + 2, j)
    
58.     [a1].CurrentRegion = ""
    
59.     [a1].Resize(j + 1, n + 3) = WorksheetFunction.Transpose(c)
    
60.    
    
61. End Sub

复制代码

整料分割方案.rar (13.74 KB, 下载次数: 53)

2013-11-9 19:25 上传

点击文件名下载附件

香川群子

我以前提过类似的问题……一定数额的金额，要求拆分成各种票面的币值，求全部组合方案。

可惜无人理睬。
http://club.excelhome.net/thread-793469-1-1.html

香川群子

henryw 发表于 2003-10-15 08:02
所以我总是怀疑题目说的或许是，对于101,201,301,401四种都是有规定出产数量的，要满足这些规定出产数量，求 ...

如果是这样的要求，会更复杂……

但其实也是可以这么来思考的：
挑选其中需求量最大的料，从有限的固定长度分配方案中找到对于此料效率最高的方案，
优先处理。

这样，到最后剩余料就会变得很少，几乎等价于基本方案的组合了。