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

dalin123

文件保存问题

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




急需参考答案！  主要思路  。。。。  感谢！

pengxiangda

整数0—1规划易想到，但实现起来并不大容易。
我想用贪婪算法也能实现，其原理是每次挑能搁进最大的文件向软盘里储存。我在这里不能从理论上证明该算法一定能得到最优解，直观上感觉是有效的，仅当作参考。
用Matlab实现了该算法，附在下面，因时间的关系代码写的并不简洁，望批评指正

1. C=input('请输入软盘的容量（以MB为单位）：');
   
2. C=C/1024;
   
3. A=input('请输入所要备份的文件的大小（由大及小，用向量来表示，例如题目中的文件应表示为[388 372 364 253 164 137 114 108 87 62 55 46]，编号1-12）：');
   
4. n=0;
   
5. 
   
6. while sum(A)~=0
   
7. C=1475;
   
8. i=1;j=1;
   
9. m=1;
   
10. D=[];E=[];
    
11. while C>0 & i<numel(A)+1
    
12. C=C-A(i);
    
13. if C<0 & i==numel(A)
    
14. D(m)=A(i);
    
15. end
    
16. if C<0 & i<numel(A)
    
17. while C<0 & i<numel(A)
    
18. 
    
19. C=C+A(i);
    
20. C=C-A(i+1);
    
21. if C<0 & i<numel(A)
    
22. D(m)=A(i+1);
    
23. m=m+1;
    
24. else
    
25. E(j)=A(i+1);
    
26. En(j)=i+1;
    
27. j=j+1;
    
28. end
    
29. i=i+1;
    
30. end
    
31. else
    
32. E(j)=A(i);
    
33. En(j)=i;
    
34. j=j+1;
    
35. end
    
36. i=i+1;
    
37. end
    
38. n=n+1;
    
39. n=int8(n);
    
40. A=D;
    
41. disp('-----------------------------------------------------')
    
42. disp('第')
    
43. disp(n)
    
44. disp('张软盘所放的文件为：')
    
45. En
    
46. disp('所放的文件的大小为：')
    
47. E
    
48. end
    
49. disp('-----------------------------------------------------')
    
50. disp('所需软盘的个数：')
    
51. n

复制代码

lijiustc

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

lijiustc

整数规划~~