孔 孔明.net Unregistered / Unconfirmed GUEST, unregistred user! 2008-03-14 #1 一张光盘可以刻录4500MB,现在有几十个大小不等的文件,求一个算法把这些文件分配到N张光盘中,要求每张光盘文件组合的大小最接近4500MB,以达到最节省光盘的目的
W wolf_cyj Unregistered / Unconfirmed GUEST, unregistred user! 2008-03-14 #2 理想状态自然是只需要总大小除以4500 再加1张光盘。 1. 首先我们可以假设这些文件最大的不会超过max_size = 4500。 2. 那么我们就得到了一个可以排序的序列， s1>=s2>=....>=sm，假设文件个数为m，最小的文件大小为sm.并且根据1我们知道 s1 < 4500。可以简单化如下处理： 从s1开始，找到s1+s2+...+sn<4500<s1+s2+...+sn+剩余最小的一个（就是sm）的一个子序列。. 每次取出这些数以后，剩余的数重新排列，重新开始寻找。 这样做应该比较简单，但未必是最优结果。
理想状态自然是只需要总大小除以4500 再加1张光盘。 1. 首先我们可以假设这些文件最大的不会超过max_size = 4500。 2. 那么我们就得到了一个可以排序的序列， s1>=s2>=....>=sm，假设文件个数为m，最小的文件大小为sm.并且根据1我们知道 s1 < 4500。可以简单化如下处理： 从s1开始，找到s1+s2+...+sn<4500<s1+s2+...+sn+剩余最小的一个（就是sm）的一个子序列。. 每次取出这些数以后，剩余的数重新排列，重新开始寻找。 这样做应该比较简单，但未必是最优结果。
W wolf_cyj Unregistered / Unconfirmed GUEST, unregistred user! 2008-03-14 #4 和典型背包有点不同吧，属于变形，如上的算法可以用比较简单的取得一个近似解。
P power255 Unregistered / Unconfirmed GUEST, unregistred user! 2008-03-14 #5 1、先取最大的文件sm， 2、在剩余空间找到最接近4500-sm的文件 3、重复第二步，直到剩余空间小于最小的文件容量。
W wolf_cyj Unregistered / Unconfirmed GUEST, unregistred user! 2008-03-14 #6 可以在每次场景定下后，尝试几种不同的选择，从大到小选择（2楼）；从小到大选择，从剩余最合适选择（5楼），最后根据三种选择的结果选择本场景最优秀的选择。
