文件分配储存问题

《文件分配储存问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、文件分配储存问题一、问题的提出将16个不能压缩的大小分别为：46KB，55KB，62KB，87KB，108KB，114KB，137KB，164KB，253KB，364KB，372KB，388KB，406KB，432KB，461KB，851KB的文件分别存放在若干个软盘上（软盘的数量足够多），每个空白软盘的容量是1.44MB，试建立优化模型在用最少的软盘的同时将所有文件分别储存进去。二、模型假设1、所有文件不能分割；2、在1M=1024KB的理想情况下考虑问题；3、各个软盘之间无明显差别；4、软盘大小固定，容量不可再扩充；5、一个文件的

2、存储不受另一个文件的影响；6、文件存储不受存放顺序的影响。三、符号说明n:文件的个数（由题可知为16）；m:分配文件所需的软盘的数目；q:软盘的空间大小；:存储标记变量；：为软盘剩余的空间大小。第19页共20页文件分配储存问题四、模型的建立和求解软盘存储文件是在计算机刚开始使用时一种常用的存储方式，它在存储过程中起着重要的作用。提高软盘空间的利用率意味着用同样多的软盘可以存储更多的文件，这对实际生活有很大帮助。提高软盘利用率的途径就是尽量减少软盘的剩余空间，下面将用多种模型分别得出最优的分配方案，使不同的文件存储在相应的软盘中，且软盘

3、数最少。一、模型建立模型一（0-1整数规划模型）：从提高软盘利用率方面来说，减少不存储空间，用最少软盘存储同样多的文件是最有效的方法。这就要求采取软盘与文件的匹配原则，充分提高软盘的利用率。1、若第个文件放在第个软盘中记为=1，其余不储存文件的软盘=0（）可得约束条件：2、由于软盘空间大小固定，可知加入软盘文件大小总和不能超过软盘空间大小即得约束条件：3、由假设可知文件不可分割，每个文件必须且只能分配在一个软盘中即得约束条件：对问题进行分析可知，若所用软盘的数量越多，则文件分配后软盘所剩余的总空间一定越大，则由此建立分配方案关于所需软

4、盘数目的函数关系所以可得模型一：第19页共20页文件分配储存问题目标函数：Min约束条件：上述建立了0-1整数规划模型来求解题中所给文件分配问题，运用C语言求得结果（见模型求解）。模型二（逆序法）：假设软盘的空间就是1.44MB。从第一个软盘开始，每一个文件或者被放入，或者不被放入，只有两种选择。如上述，我们考虑逆序的方法：即先把最大的文件放入第一个软盘中，若软盘不满，再放入余下中最大的，若软盘不满，则依此类推，若软盘已满，则放入下一个软盘……在上述讨论的基础上，我们可以知道所需的软盘数目有可能是=3个，也有可能是4个，也有可能是更多

5、。现在我们采用逆序的方案来进行求解：首先在第一个软盘中选取16个文件中最大的文件：851KB，再选取剩下的15个文件中最大的文件：461KB，此时软盘剩下的空间为162.56KB，故只能在剩余的文件中选取文件大小为137KB的文件了，共计1449KB，第一个软盘剩余空间为25.56KB；用同样的方法可得第二个软盘中放入的文件大小为432KB、406KB、88KB、164KB、62KB的文件，共计1452KB；在第三个软盘中放入372KB、364KB、253KB、114KB、108KB、87KB、55KB46KB，共计1399KB。使用

6、软盘数最少为3个。上述建立了逆序法的模型求解题中所给文件分配问题，我们还可以运用C语言求得结果。第19页共20页文件分配储存问题模型三（遍历法）：首先，放进去的文件的顺序是没有影响的，因为最后所有的文件必然都会被放进去，而且又因为都被放进去，所以最先放哪个文件都是可以的。于是我们可以这样认为，把所有的文件按顺序编号1到16,并假设最先放进去的是1，然后我们可以放2到16共15种放法，我们记录每一种组合的结果，然后对每一个情况都重复这样的一个步骤，即比如说第一步放了1，第二步我们放了2，接下来做试探，即从3到16都尝试，取得最小值，同时

7、对第二步的其它放法也做同样的试探。依次类推，用这种算法我们可以得到所有的组合，即我们可以从中得到整体最优的组合。每一步我们都遍历所有的可能，取得最优解，而在下一步的时候利用上一步最优化的组合，使得所用的软盘数最少。上述用遍历法思想求解题中所给文件分配问题，运用C语言编程可求得结果（见模型求解）。一、模型的求解模型一（0-1整数规划模型）的求解：将题目所给文件的大小按降序排序，即：,设计搜索算法，运用C语言编写程序求解模型一得出最优结果如下表所示：编号剩余空间(KB)所装文件（KB）125.56851、461、137222.56432、

8、406、388、164、62375.56372、364、253、114、108、87、55、46模型二（逆序法）的求解：采用逆序法运用C语言编程算出的最佳组合如下表所示：编号剩余空间（KB）所装文件（KB）125.568