回 帖 发 新 帖 刷新版面

主题:[讨论]遇到的一个数学问题

在我的电脑里 有1000G的内容需要刻录成DVD数据保存,大家知道,一张DVD的容量为4500MB(大概4.35GB),问题是1000GB内容,里面包含各类文件,电影、相片、Mp3,软件安装包等等,上千万个,单个文件大小最小的1KB 最大的6.5GB,大小不一,现在的做法是 先把单个文件超过4.35GB 的大文件归在一起,另作处理(毕竟不是太多),然后 框选几个文件 看看,是超过还是低于4.35GB ,超过了再去掉几个,不够再添上几个文件,这样凑够大概4.35GB之后,刻录一张DVD,可是这样来回筛选,刻录工作量很大,尤其这个来回筛选过程很费时间。我尝试了其他办法,我可以用简单的Dos命令 或者小软件 轻易获得每个文件的具体大小列表,把问题 抽象一下,就是“和”是固定的 限定的一个值,每个加数 都已知确定(在一个范围内 但大小不等),如何把这些加数 筛选(每个加数只能出现在一个堆里,不能重复使用) 归成一“堆”一“堆”,使每个“堆”和小于限定“和”,(但要接近这个限定“和”,比如4.35GB,每堆文件大小和 可以使4.33GB ,4.32GB,4.3GB,4.28GB。。。如果不接近这个和,比如只装3GB,那么一张DVD空间浪费太大了), 
我想用Excel表格 做个试验,在A列使用随机函数 随即生成100个0.1-9.95这样大小的数值,然后通过分堆 限定和值为7.5 ,然后进行分堆,先把大于等于7.5的值 放到一边,分好组后,让电脑把各个堆组数值标记成不同颜色, 
不知道 这属于 什么问题?这个实验 能通过 Excel 实现吗?
注意几点:1、这么多文件中肯定有偶尔 几个文件碰巧相等的情况;
2、某个文件自身大小就是4.32GB,该文件独占一张DVd ,
3、分堆的结果应该是多样的,不是单一的(要求接近和,例如a=1,b=2,c=3,d=3,e=4,f=5,和限定为6,可以分为三堆,af一堆,be一堆,cd一堆,也可以分为abc一堆,d,e,f单独各占一堆,共四堆,显然前一种分发好一点,后一种空间浪费多,几种结果也可能存在的浪费一样多)
在网上 看到了类似的数学建模问题,说 某铸造工厂仓库有一批大量零件,单件重量从10g-200kg不等,每个零件贴有条形码,重量在数据库中已知,传送带小车 每次最大载重50Kg,先分堆,在运输,怎样实现自动归堆??

回复列表 (共1个回复)

沙发

我个人的想法是这样的,前提假设你的文件小于你所限定的和。
1. 由大到小排序
2. 设一差值变量C,初值为限定和,在文件列表中寻找小于等于C的最大文件N[i],标记此文件,C=C-N[i],寻找第二个文件,第三个文件,...,直至C=0或者C的值小于最小文件的大小。上述所得文件列表即为一张DVD。
3. 在剩下的文件寻找第二张DVD文件列表
4. 重复上述步骤
时间复杂度等于排序的时间复杂度,如果程序写得熟的话,是能够实现的。
这个并不是最好的算法,1000G(文件全部小于刻录盘)的理论值是1000/4.35=230张,这个算法应该能够比较接近了

我来回复

您尚未登录,请登录后再回复。点此登录或注册