有点急，帮朋友问，暂时还想不出来，大家帮帮忙，谢谢
有无数根原料，每根250米，每天用户提出一些需求，切割这些原料，比如
30米的5根
20米的5根
10米的5根
40米的5根
50米的5根
那么我怎么切才能使250米的原材料损耗最小呢？怎样排这个顺序呢？
以上是假设数据，米数和根数是随机的，用户需求数也不一定是5个，可能更多。。
请问如何做呢？
环境：
declare @tbl table(a int,b int)
insert @tbl values (30,5)
insert @tbl values (20,5)
insert @tbl values (10,5)
insert @tbl values (40,5)
insert @tbl values (60,5)
select * from @tbl
我想要的结果是：
假设啊，先从30米的那里切，切根，然后切10米的根，然后切30米的根，然后切20米的n根，然后切50米的根.......
---------------------------------------------------------------
有难度,顶一下
---------------------------------------------------------------
up only
---------------------------------------------------------------
没完全理解!
---------------------------------------------------------------
背包问题,有算法的
---------------------------------------------------------------
这个用一般的数据库操作是没办法做的，这是一个典型的线性规划问题，解决这种问题跟数据库操作没什么关系，主要是算法的问题，现在这类问题一般都是用单纯形法来解决。
方法简单介绍一下，就是先建立数学模型，通过行列矩阵和单纯形表的操作，最后得到最优解。
你这个需求有一些地方没定义清楚：
1）什么样叫损耗最小？从数学角度如何表达？
2）余下的边角料是否也参与下一次的切割？
我对用数据库来完成单纯形法的运算很感兴趣，前段时间也想做下这方面的研究，不过我最近有项目在身，比较忙，就把这个事放下了，如果你有兴趣可以与我联系。
---------------------------------------------------------------
我的理解：
1）应该是每个250m切后余量最小
2）余下的边角料当然会参与下一次的切割
这个问题与那个大箱装小箱的问题有点类似，关注
---------------------------------------------------------------
这些问题都是NP问题,一般没有办法得到最优解,用贪婪算法可以得到次优解
简单地做就是先截最大的,余下的再截.最后剩下的部分就作废.
---------------------------------------------------------------
给你个连接参考
http://www.vcok.com/class/list.asp?id=306
---------------------------------------------------------------
还有一种做法适用于切割量是数字的那种.比如说250米只有可能有50 60 30 20 四种切割方法.那么就有可能一点也不浪费(前提是要允许在某个中间阶段有多个半节的管子存在)
---------------------------------------------------------------
这个跟背包问题不一样的，虽然都是在运筹学的研究范围内。这个问题可以建立线性模型，背包问题是没办法建立这样的数学模型的，背包问题的解法与这类问题的解法思路是完全不同的。现在线性规划问题已经有单纯形法能很好地解决，也是比较容易用计算机来实现的。
如果只是一个确定的问题，其实可以用EXCEL表格将数学模型建立起来，用EXCEL里的加载宏“线性规划”求得最优解。但若是每次要用新的数据来计算，就不好用EXCEL来一个个做了。所以需要用程序来建立数学模型，并完成单纯形法的算法。
---------------------------------------------------------------
使得每一根截取后剩余长度最小：
第一步：
minZ=250-10X-20Y-30Z-40P-50Q
X<=5
Y<=5
Z<=5
P<=5
Q<=5
第二步：直到到其中的一种截完,比方说是50的
minZ=250-10X'-20Y'-30Z'-40P'
X'<=5-X
Y'<=5-Y
Z'<=5-Z
P'<=5-P
如此反复，直到取完....
解上面的方程，一根一根地排.
所谓损耗最小，也就是剩下的最小，上面的方程用几个循环应该可以算出
---------------------------------------------------------------
这个类似于以前的一道数学建模题.
---------------------------------------------------------------
这应该是一个算法问题.如果说单从这一次操作来说:
它就是从寻找一个总量最大化的集合(小于等于250),重复执行,直到没有可选项;
如何寻找最大化集合:
---------------------------------------------------------------
我觉得excel算不出来，
我已经把方程列出来了，那就是运筹学里的东东。至于单纯形法，也没必要用到那个来算.
---------------------------------------------------------------
工具->加载宏->，里面的规划求解是不是？
---------------------------------------------------------------
应该有吧，我用office2000里的规划求解解你这个题，得到的最优解是：
第一根 第二根 第三根 第四根 第五根
切10米的N根 1 1 1 1 0
切20米的N根 0 0 0 0 1
切30米的N根 0 1 1 1 1
切40米的N根 6 4 4 4 5
切50米的N根 0 1 1 1 0
因为理论上不做最优化，最多只要五根肯定够了，所以我用五根为基础来建立数学模型。
你在excel里选择菜单“工具”-“加载宏”。选择“规划求解”就可以了。如果没安装会调出OFFICE的安装程序的。
---------------------------------------------------------------
我解题的过程见图片：
http://www.freewebs.com/icevi/sample.JPG
表格中的1只是预设值，无意义。点击“求解”后就得到了上面的结果。
---------------------------------------------------------------
这的确是一个困难的问题，同时也是一个比较有意义，有意思的问题。
可以建模来解，关键是实现的算法可能较为复杂。实现起来应该不会很难。
回去思考一下
---------------------------------------------------------------
真能算得出来？不是吧？想当初我做那道类似的建模题花了不少时间。