200908网友练习《最优化问题》

dalin123 发表于 2009-8-17 16:34

本帖最后由为你奋斗于 2009-12-3 15:35 编辑

 文件保存问题 在出发去度假之前，你希望将你的一些最重要的文件备份到软盘上。每个空白软盘的容量是1.44MB。你需要备份的16个文件的大小分别为：46KB，55KB，62KB，87KB，108KB，114KB，137KB，164KB，253KB，364KB，372KB，388KB，406KB，432KB，461KB，851KB。假定你无法使用压缩软件，但软盘数量足够，那么应如何将这些文件分配到每一张软盘上才能使使用的软盘数目最少？ 急需参考答案！主要思路。。。。感谢！

lijiustc 发表于 2009-8-17 17:16

整数规划~~

lijiustc 发表于 2009-8-17 17:17

对于整数规划应该有现有程序可解的~~~~
应该是这样了~~~问题不难（？我只是随便看了看~~~~回答不当，楼主别生气哈~~~~呵呵）

pengxiangda 发表于 2009-8-18 18:09

整数0—1规划易想到，但实现起来并不大容易。
我想用贪婪算法也能实现，其原理是每次挑能搁进最大的文件向软盘里储存。我在这里不能从理论上证明该算法一定能得到最优解，直观上感觉是有效的，仅当作参考。
用Matlab实现了该算法，附在下面，因时间的关系代码写的并不简洁，望批评指正
C=input('请输入软盘的容量（以MB为单位）：');
C=C/1024;
A=input('请输入所要备份的文件的大小（由大及小，用向量来表示，例如题目中的文件应表示为，编号1-12）：');
n=0;

while sum(A)~=0
C=1475;
i=1;j=1;
m=1;
D=[];E=[];
while C>0 & i<numel(A)+1
C=C-A(i);
if C<0 & i==numel(A)
D(m)=A(i);
end
if C<0 & i<numel(A)
while C<0 & i<numel(A)

C=C+A(i);
C=C-A(i+1);
if C<0 & i<numel(A)
D(m)=A(i+1);
m=m+1;
else
E(j)=A(i+1);
En(j)=i+1;
j=j+1;
end
i=i+1;
end
else
E(j)=A(i);
En(j)=i;
j=j+1;
end
i=i+1;
end
n=n+1;
n=int8(n);
A=D;
disp('-----------------------------------------------------')
disp('第')
disp(n)
disp('张软盘所放的文件为：')
En
disp('所放的文件的大小为：')
E
end
disp('-----------------------------------------------------')
disp('所需软盘的个数：')
n

页: [1]

数学建模社区-数学中国's Archiver

200908网友练习《最优化问题》