2011年应届生落户工作Q&A问题汇总

《2011年应届生落户工作Q&A问题汇总》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2009年华中地区数学建模邀请赛B题文件保存问题11交运1班秦国阳11交运1班杨儒东11交运2班徐茂源摘要本文围绕文件保存问题，利用数学建模中线性规划是的方法，以及C++,Matlab软件，来解决在软盘数量限制的情况下，合理组合解决利用最少软盘将全部文件储存的难题。本题的决策变量为“某个文件是否存储在某个软盘上（若存储在软盘上用1表示，没存储上用0表示）”，约束条件是“每个软盘的容量大小有一定的限制，每个文件只能存储在一个软盘中。”目标函数为“每个文件的大小与决策变量（1或0）乘积求和的最小值。关键词：线性

2、规划，0-1规划，动态规划，C＋＋,枚举法,Matlab,bintproq命令，系数矩阵一．问题重现在出发去度假之前，你希望将你的一些最重要的文件备份到软盘上。每个空白软盘的容量是1.44MB。你需要备份的16个文件的大小分别为：46KB，55KB，62KB，87KB，108KB，114KB，137KB，164KB，253KB，364KB，372KB，388KB，406KB，432KB，461KB，851KB。假定你无法使用压缩软件，但软盘数量足够，那么应如何将这些文件分配到每一张软盘上才能使使用的软盘数目

3、最少？标注：1.44MB=1474.56KB1474KB16个文件的总的容量为：4300KB二．问题分析本题研究的是用最少数量的软盘将这16个文件储存进去，根据所给的条件，我们可以得出16个文件的总容量为4300KB，每个软盘的大小为1474KB，用=2.9，不可能将这些文件存储在2个软盘中，同时很容易将16个文件存16储在4个软盘中，所以我们假设最少也需要三个软盘。综合以上分析我们用线性规划中的0-1规划对假设进行论证。设决策变量表示文件i是否存入磁盘j，即（i=1,2,3….16j=1,2,3）1，当第

4、i个文件存入第j个软盘中0，当第i个文件不存入第j个软盘中中=每个文件放在一个软盘中的约束为：每个软盘的容量一定（1474KB）的约束为：………….目标函数为每个文件的大小与决策变量（1或0）乘积求和：16三．符号说明(1)将16个文件依次序标注为：；(2)将16个文件的文件大小依次序标注为：；(3)表示文件i是否存入磁盘j；四．模型的建立与求解4.1模型的建立该问题的模型为0-1规划模型(j=1,2,3)s.t4.21用Matlab对模型进行求解用Matlab求解本题，运用的主要思想是构建一个系数矩阵，利

5、用bintproq命令直接对矩阵进行求解，得出的结果为每三个一组的0,1代码，也相当于一个位置矩阵，比如某个文件的矩阵结果为010，表示该文件在第二个软盘里，但是Matlab只能求出一种结果。根据Matlab编程可得：X=16010，010，010，010，001，010，010，010，100，100，010，001，010，001，001，100磁盘1磁盘2磁盘3（9）253（10）364（16）851（1）46（2）55（3）62（4）87（6）114（7）137（8）164（11）372（13）40

6、6（5）108（12）388（14）432（15）46114431389用Matlab解出的结果只有一种情况，但是我们猜想把16个文件存储在3个软盘中不可能只有一种情况，应该有很多种组合方式，这可能是由于Matlab软件的局限性造成的，因此我们考虑用另外一种软件C++对本题进行求解。4.22用C++对模型求解我们用C++对本题进行求解，编程的主题思想为枚举法，所谓枚举法就是在数学问题里，有一些计算总数或种类的问题，很难用传统的方法去解答，感到无从下手，对此，我们可以先估计其总数的大小，若数目不大，就可以按照

7、一定的顺序一一列举问题的可能情况；若数目过大，我们就抓住适当的标准，把问题分为有限种情况，分别采用枚举法，最终达到目的，也叫做列举法或穷举法。使用0-1原则，根据约束条件由的系数，可得位置矩阵且16；由约束条件方程组得到，文件的位置矩阵如（例子不一定合乎条件）根据上述位置矩阵，便能得到一种分配方案。在VC++编程过程中，为了优化运算，设置了变量x[i]来表示文件i存放的存放位置：虽然将磁盘分为磁盘1、磁盘2以及磁盘3，但实际上磁盘不应有顺序之分，故在计算结果时，除以排列数，得到实际方案总数。16根据C+编程

8、计算可得：注：实际结果远不止10种，此为输出结果的部分截图。方案总数为：16总共有种解决方案（为3个磁盘所有排列数，由于磁盘存放无顺序区分，故将运算结果总数除以，得到实际方案总数。）16个文件存入3个磁盘的一些方案磁盘1磁盘2磁盘31474.56KB1474.56KB1474.56KB方案一(7)137(15)461(16)851(3)62(8)164(12)388(13)406(14)432(1)46(2)55