B题第一问的结果大约800块

zhudy

<>B题第一问的结果大约800块,网上有人讲799块，因为没有看到具体的方案，还无法作出评价。至于下料方式可以少至34种，但材料利用率要下降。 </P>
<>本题的主要标准应该是思想，结果是第二位的，不知大家以为如何？仅一个具体问题有好的结果，不一定说明方法就是好的。要看对大量的具体问题是否都有好的结果。</P>
<>本题的评审标准也一定要看结果。有同志在网上发表意见，认为B题没有创造性，对此，我有不同的看法，要得到本题的一个结果的确很容易，极端情况每块料只用一次，其余都浪费。但是在810块的基础上每减少一块，也要付出很大的努力，而且越来越困难。特别让你的思想有普遍意义更是一件难事。这是一个公开问题，我想一般研究生还到不了看轻这个问题的水平。</P>

easyworm

<>呵呵，<b><FONT color=#000066>starfish言之有理啊</FONT></b></P><><b><FONT color=#000066>算法能做到兼容性好，是很不容易的，对于下料算法，还有很有搞头的</FONT></b></P>

shumo123

< 150%? LINE-HEIGHT: 24pt; TEXT-INDENT: 0pt; 0cm>朱老师：我们的结果是：</P>< 150%? LINE-HEIGHT: 24pt; TEXT-INDENT: 0pt; 0cm>一维：原材料总数：<B><FONT face="Times New Roman">801</FONT></B><B>块</B>；下料方式共计：<B normal?>30种</B>；</P>< LINE-HEIGHT: 24pt; TEXT-INDENT: 0pt; 0cm 2.0? mso-char-indent-count: 150%;>二维：原材料总数：<B><FONT face="Times New Roman">454</FONT></B><B>块</B>；下料方式共计：<B normal?><FONT face="Times New Roman">21</FONT></B><B normal?>种；</B></P><P LINE-HEIGHT: 24pt; TEXT-INDENT: 0pt; 0cm 2.0? mso-char-indent-count: 150%;><b>通过验证是可行的。</b></P><P LINE-HEIGHT: 24pt; TEXT-INDENT: 0pt; 0cm 2.0? mso-char-indent-count: 150%;><b>你所需要的是用来验证数据可行性的程序，包括每种方式下余料不为负、需求材料的数量、紧急材料制作时间是否满足？</b></P>

starfish

我觉得B题的评判不应光看答案
这个问题本来就是NP完全问题
如果仅仅看最后的结果没有多大意义
更重要得是计算出该结果的算法是否实用
很多人都是用整数规划或其它剪枝搜索算法计算了一两个小时或一两天才算出一个很好的结果
这样的算法并不实用
现实中没有那个单位会为了省几根材料而花一两个小时甚至一两天来计算
事实上用最简单的BFD算法可以在1秒之内对第一问算出709根的结果
虽然这个结果不是最优，但这个算法是最实用的

我觉得评判的标准应该是对算法的效率和性能的分析
以及各种规划模型的具体构造
如果仅仅把此问题归约为TSP用各种优化算法求解并没有多大意义
任何优化算法都是针对某些具体数据作优化的
也许该算法对于这题的数据恰好能给出很好的结果
但对于其它数据可能结果会很差
而实际生产中任何数据都可能遇到
所以算法的评判标准应该是该算法的近似比
即“该算法所计算出的结果/实际最优结果”这个比值在最坏情况下的上界
这个界越接近1说明该近似算法性能越好

事实上，下料问题和背包问题已经被计算机科学家研究的很透彻了
各种近似算法的近似性能也有了很多结果
说实话，我们的论文并没有太多原创的东西
但我们参考了大约100多篇论文
对各个已知结果作了一个比较系统的综述
由于这个问题最近50年来已经被研究的非常透彻
几乎所有能想到的方法都已经有人做过了
所以不太可能在三天内想出新的算法
我们觉得
与其专门针对此题的数据用各种已知的算法进行优化和实验
还不如系统地分析目前已有的结果
并比较分析其优劣和适用条件
选择最合适的在实际中使用

wilse

第二问得结果是多少？