[讨论]一个由刻录碟片引发的问题&_&

FantasyDR

啊～～！期待思路详解或者源码...

优先保证尽量填手头的这张碟片，而不考虑下面一张碟片么？需要回溯么？

Eastsun

以下是引用Lendy在2005-8-15 13:47:33的发言：<br>写了一个试验品，可以算出顶楼的最佳方案。
用这种思路写：怎么放才能使每张光盘所剩的空间最少。
[attachment:3877]

有点怀疑这种思路的正确性...
我有两种想法,不过时间复杂度都不是多项式规模的.
1.用迭代加深搜索算法
   显然磁盘个数有一个下界:   文件总容量/单个磁盘容量
   从这个值开始依次尝试增大直到找到一个符合要求的解为止,这个解肯定是最优的.
2.用动态规划
   假设(A11,A12,...A1N1),(A21,A22,....A2N2),...(Am1,Am2,....,AmNm)
   是一个满足条件的最优解序列.
   我们可以在这个假设的前提下使用动态规划:
   令  S[i,j]  表示序列中第i到第j个文件最少需要的磁盘数量.
   则有:
      a.      Bi+...Bj<=磁盘容量           ,S[i,j]=1                  (Bi表示序列中的第i个元素)
      b.      否则        S[i,j]=min{      S[i,k]+S[k+1,j] |      i<=k<=j-1}   
   这样可以得到一个动态规划的算法,时间复杂度是 O(n^3)
但是,n个文件共有n!种排列....
所以直接用这种算法是不实际的.不过我们可以看到:如果  Ai,j 是满足条件的一个序列.
那么将Ai,j 按各个磁盘打乱,或将各个磁盘内的文件序号打乱,依照这种算法依然可以求得最优解!  何况最优解很可能不止这一种情况.
也就是说,从直观上看,任意给出文件的一个排列,存在最优解的概率不会太小(也不大..),所以可以这样:
  每次将文件序列随机重排一下序,然后用上面的算法求得这种情况得最优解.
  只要这个过程进行的次数足够大,那么最优解中的最小值很可能就是整体最优解...

[此贴子已经被作者于2005-8-15 19:44:34编辑过]

Lendy

以下是引用Eastsun在2005-8-15 17:18:39的发言：<br>

1.用迭代加深搜索算法
2.用动态规划+随即分布

感觉楼上说的这两种方法都不妥……
第一种不用多说了……说白了就是穷举。这个问题用穷举，估计测算10个文件就会死机。
而第二种方法，这道题不能这样用动态规划，因为上文没有找出明确的最优化策略。
不过看后面那段，楼上的思路应该就是直观考虑“怎么使所用盘数最少”。

那么，回过头说这种思路：“怎么放才能使每张光盘所剩的空间最少”。
----------------------------------------------------------------------------------
暂不详细讨论这种思路能不能求出最优解，只举个简单例子：
人工测算数据里，剩余空间最多的一张光盘是：[634MB](A)
而用程序测算的数据，剩余空间最多的是：[626.81MB](B)
那么，假如再放入一个70MB的文件，光盘(A)就已经放不下。
也就证明在这两种情况中，程序测算出来的是优解。
----------------------------------------------------------------------------------
考虑这种思路，有必要先明确一点：只要在某张光盘里放进一个文件，那么这张光盘所能装得下的最大文件总量就已经可以确定。
即使有多种安排文件的方案，但只要最大文件容量是一样的，就可以视为同种情况考虑（这个很难解释得清，只可意会了…）
那么，照这种思路，逐张光盘安排文件，最后便能得到唯一最优解。
而如果是考虑“所用盘数最少”，那么最优解就会出现多种情况。
PS: 其实这个问题很直观就会想到动态规划。也应该可以用动态规划，找时间再继续尝试最优化策略。
PS2: 匆匆回了帖，因为要外出…… -_-b 有什么不清楚的地方，晚上回来继续讨论。

Eastsun

以下是引用Lendy在2005-8-15 19:34:36的发言：[BR]
而第二种方法，这道题不能这样用动态规划，因为上文没有找出明确的最优化策略。

不太明白这句话的意思...
ps;貌似这个问题就是著名的NP难题"装箱问题"

装箱问题也就是把一定数量的物品放入容量相同的一些箱子中，使得每个箱子中的物品大小之和不超过箱子容量并使所用的箱子数目最少。其应用在实际生活中无处不在，货物装运，服装裁剪，以及我们计算机科学中的存储分配、共享资源调度、文件存储都是装箱问题在实际应用中的体现。所以装箱问题有着广泛的应用背景，具有很大的研究价值。
装箱问题是经典的NP难解问题，这意味着该问题不存在在多项式时间内求得精确解的算法（如果P≠NP）因此对装箱问题算法的研究指的是对其近似算法的研究，所谓近似算法即该算法可以求得与精确解接近的结果但不一定得到精确解。目前，已经提出了大量的近似算法，如下次适应（Next Fit）、首次适应（First Fit）、最佳适应（Best Fit）、调和（Harmonic-K）算法等[BR]

FantasyDR

呀...-_-b
诡异了……

FantasyDR

我们知道,一般的CD-RW容量是700mb.
假设手头有n个文件,每个文件的大小都在700mb以内.现在需要把这些文件都刻录到光碟上面去.

那么,怎样分配这些文件,才能使消耗的光碟数量最小呢?

自己想了很久发现总是算错...-_-b谁能提供一些思路呢?

附上一组测试数据,据我脑力估算,可以在9张碟片之内刻录下面的32个文件:
{415.87
410.85
397.8
383.14
381.53
377.06
358.5
334.81
309.55
300.34
282.54
278.73
231.84
213.94
188.46
181.03
172.73
168.35
166.42
166.09
154.97
145.41
137.4
1.07
0.83
0.3
0.01
0.01
0.01
0.01
0.01
0}
但是自己写的程序说要10张.不爽ing...