7,763
社区成员
发帖
与我相关
我的任务
分享有些难度哦！一个算法问题
假设某工地需要的钢材都是 10m/根 的原材料
现在因建筑需要要下列长度钢材
5.5m 4.7m 4.2m 3.7m 1.1m 7.0m 3.0m
切剩的料为废料
请设计一个算法，如何组织切割这些钢材
要求：尽量使废料集中到最后一根，且需要根数最少
如上述应该是
4.2+4.7+1.1 / 废料 0
7.0+3.0 /废料 0
5.5+3.7 /废料 0.8
现在因建筑需要要下列长度钢材
5.5m 4.7m 4.2m 3.7m 1.1m 7.0m 3.0m
切剩的料为废料
请设计一个算法，如何组织切割这些钢材
要求：尽量使废料集中到最后一根，且需要根数最少
如上述应该是
4.2+4.7+1.1 / 废料 0
7.0+3.0 /废料 0
5.5+3.7 /废料 0.8
...全文
请发表友善的回复…
发表回复
xxfeiyu 2004-09-05
- 打赏
- 举报
..................
lazygod 2004-08-08
- 打赏
- 举报
背包问题的一个变化，在google搜一下“背包问题”就可以解决了
xxfeiyu 2004-08-08
- 打赏
- 举报
up ...............
xxfeiyu 2004-07-21
- 打赏
- 举报
up
xxfeiyu 2004-07-21
- 打赏
- 举报
up .
null1027 2004-07-18
- 打赏
- 举报
从一组数据里取得合刚好等于某数的组合的算法：
function Sum(byref data() ,iBegin as interger,iSum as interger) as string
'参数描述 data是存储数据的容器 ibegin是搜索的开始位置，isum是要得到的合
sum = ""
for j=ibegin to ubound(data)
for i = j+1 to ubound(data)
if data(j) +data(i)=isum then
sum = sum & data(j) & data(i)
data(j)=0
data(i)=0
给序号从j开始后面的数排序
exit function
else if data(j)+data(i)<isum then
sum = sum & Sum（data,i，isum-data(j))
end if
next i
next j
end function
大致就这样了吧,关键是想法,这样的代码肯定不可以.
function Sum(byref data() ,iBegin as interger,iSum as interger) as string
'参数描述 data是存储数据的容器 ibegin是搜索的开始位置，isum是要得到的合
sum = ""
for j=ibegin to ubound(data)
for i = j+1 to ubound(data)
if data(j) +data(i)=isum then
sum = sum & data(j) & data(i)
data(j)=0
data(i)=0
给序号从j开始后面的数排序
exit function
else if data(j)+data(i)<isum then
sum = sum & Sum（data,i，isum-data(j))
end if
next i
next j
end function
大致就这样了吧,关键是想法,这样的代码肯定不可以.
xxfeiyu 2004-07-18
- 打赏
- 举报
也许是2段刚好
但是，也可能是5段才刚好呢？
但是，也可能是5段才刚好呢？
jiang8360 2004-07-18
- 打赏
- 举报
up
null1027 2004-07-18
- 打赏
- 举报
从一组数据里取得合刚好等于某数的组合的算法：
sub Sum(byref data() ,iBegin as interger,iSum as interger)
'参数描述 data是存储数据的容器 ibegin是搜索的开始位置，isum是要得到的合
for j=ibegin to ubound(data)
for i = j+1 to ubound(data)
if data(j) +data(i)=isum then
debug.print data(j)& data(i)
data(j)=0
data(i)=0
给序号从j开始后面的数排序
exit sub
else if data(j)+data(i)<isum then
GetSum（data,i，isum-data(j))
end if
next i
next j
end sub
一个设想，没编码实现过，可能还有些问题，但是大致思想在这里了．
sub Sum(byref data() ,iBegin as interger,iSum as interger)
'参数描述 data是存储数据的容器 ibegin是搜索的开始位置，isum是要得到的合
for j=ibegin to ubound(data)
for i = j+1 to ubound(data)
if data(j) +data(i)=isum then
debug.print data(j)& data(i)
data(j)=0
data(i)=0
给序号从j开始后面的数排序
exit sub
else if data(j)+data(i)<isum then
GetSum（data,i，isum-data(j))
end if
next i
next j
end sub
一个设想，没编码实现过，可能还有些问题，但是大致思想在这里了．
xxfeiyu 2004-07-17
- 打赏
- 举报
你试试？
xxfeiyu 2004-07-16
- 打赏
- 举报
还没有实质性的算法吗？
chuting1 2004-07-16
- 打赏
- 举报
什么呀?
最少得说明各需要多少根,
然后求最少要买多少10米的,
如何切啊,
要不然都小儿科了
最少得说明各需要多少根,
然后求最少要买多少10米的,
如何切啊,
要不然都小儿科了
cosio 2004-07-16
- 打赏
- 举报
用树的结构来说明：
//钢材入库时，对每一根钢材进行编号,这里我是考虑到厚度不同，也可以同一类的厚度归为 一类。
10Ｍ
/ （两个） 组合等于 组合不等于 然后在用不等于中的三个组合在加等于10Ｍ
如此类推，用遍历方法来做！
//钢材入库时，对每一根钢材进行编号,这里我是考虑到厚度不同，也可以同一类的厚度归为 一类。
10Ｍ
/ （两个） 组合等于 组合不等于 然后在用不等于中的三个组合在加等于10Ｍ
如此类推，用遍历方法来做！
ryuginka 2004-07-15
- 打赏
- 举报
up
kmzs 2004-07-15
- 打赏
- 举报
算法？有没有搞奥赛的同志？陨呢？
lsftest 2004-07-15
- 打赏
- 举报
我想编程的时候还必须考虑需求量问题。。。，例如，上面楼主给出的：
现在因建筑需要要下列长度钢材
5.5m 4.7m 4.2m 3.7m 1.1m 7.0m 3.0m
切剩的料为废料
只是需求的规格，但并没有明确的说出要多少条。。。。需求量不同可能会导致结果不同。。。。
现在因建筑需要要下列长度钢材
5.5m 4.7m 4.2m 3.7m 1.1m 7.0m 3.0m
切剩的料为废料
只是需求的规格，但并没有明确的说出要多少条。。。。需求量不同可能会导致结果不同。。。。
thirdapple 2004-07-15
- 打赏
- 举报
动规不对，或者应该全搜索……
huhanshan013 2004-07-15
- 打赏
- 举报
二楼的兄台，你想简单了吧，
据我看你的程序，
先找最长的，然后到后面找，和余下的长度最接近的，当然完全相同那就没有什么了，但是不相同的你如何处理？你还是这样处理，找最长最接近的，可是你忽略了，假如余下的，两根加起来更节省了？
我的思路，回去再想程序了！
10M-最长
/ / 刚好另外一根吻合 找不到吻合的
/ / 刚好吻合，或者最接近 两根加起来吻合或者更接近
据我看你的程序，
先找最长的，然后到后面找，和余下的长度最接近的，当然完全相同那就没有什么了，但是不相同的你如何处理？你还是这样处理，找最长最接近的，可是你忽略了，假如余下的，两根加起来更节省了？
我的思路，回去再想程序了！
10M-最长
/ / 刚好另外一根吻合 找不到吻合的
/ / 刚好吻合，或者最接近 两根加起来吻合或者更接近
thirdapple 2004-07-15
- 打赏
- 举报
Dim s As Long, i As Long, j As Long, out As String
Dim a(0 To 6) As Single, b(0 To 6, 0 To 6) As Boolean, c(0 To 6) As Single
a(0) = 5.5
a(1) = 4.7
a(2) = 4.2
a(3) = 3.7
a(4) = 1.1
a(5) = 7
a(6) = 3
For i = 0 To 6
c(i) = a(i)
Next i
s = 10
For i = 0 To 6
b(i, i) = True
For j = i + 1 To 6
If a(i) + a(j) > a(i) And a(i) + a(j) <= s Then
a(i) = a(i) + a(j)
b(i, j) = True
End If
Next j
Next i
For i = 0 To 6
out = ""
For j = 0 To 6
If b(i, j) Then
out = out & CStr(c(j)) & "+"
End If
Next j
out = Left(out, Len(out) - 1) & " 废料/" & CStr(Round(s - a(i), 1))
Print out
Next i
试试看
Dim a(0 To 6) As Single, b(0 To 6, 0 To 6) As Boolean, c(0 To 6) As Single
a(0) = 5.5
a(1) = 4.7
a(2) = 4.2
a(3) = 3.7
a(4) = 1.1
a(5) = 7
a(6) = 3
For i = 0 To 6
c(i) = a(i)
Next i
s = 10
For i = 0 To 6
b(i, i) = True
For j = i + 1 To 6
If a(i) + a(j) > a(i) And a(i) + a(j) <= s Then
a(i) = a(i) + a(j)
b(i, j) = True
End If
Next j
Next i
For i = 0 To 6
out = ""
For j = 0 To 6
If b(i, j) Then
out = out & CStr(c(j)) & "+"
End If
Next j
out = Left(out, Len(out) - 1) & " 废料/" & CStr(Round(s - a(i), 1))
Print out
Next i
试试看
thirdapple 2004-07-15
- 打赏
- 举报
动态规划，待会写程序
加载更多回复（10）
