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

FantasyDR

给一组简单的测试数据:
{480,300,240,150,100,80}
总计容量是1350mb,也就是最少2张碟片可以装下.
实际安排,确实2张可以装下{480,100,80}、{300,240,150}

但是如果按照上述思路:
1、先取480，然后逐个搜索，发现只有150可以继续填充此光盘。
2、接下来选取300，依次进行，得到如下错误结果，多用了一张碟片。
{480,150}、{300,240,100}、{80}

JAY

也许可以先按大小排序，然后往“盘”里面放，放得下就放，放不下就放新的盘。可以从小的来，或者从大的来~
貌似好低级的算法~

FantasyDR

这样算,不行的...我就是这样试验的,结果是不对的.
可以试这组数据,就是错误的.

JAY

要不这样：
先按大小排序，然后都往一个盘里面放，放得下就放，放不下就试下一个数据，直到一张盘装满或者没有数据可选。然后新建一张盘，继续这样放。

JAY

从尽量减少浪费出发
{480,300,240,150,100,80}
加入480
总共480剩220，考虑一半剩余空间110，100、80小于，加入最大小于数100
总共580剩120，考虑一半剩余空间60，无小于数，考虑全部剩余空间，80小于120，加入80
总共660剩40，考虑一半剩余空间20，无小于数，考虑全部剩余空间，无小于数。
第一张碟写完{400,100,80}
剩{300,240,150}
加入300
总共300剩400，考虑一半剩余空间200，150小于，加入最大小于数150
总共450剩250，考虑一半剩余空间125，无小于数，考虑全部剩余空间，240小于250，加入250
无剩余数据。
第二张碟写完{300,150,240}

leesoft

和shjic讨论了一种算法：
先把所有文件的大小排序。每次都取出当前最大文件。如果没有盘还能容纳它，就增加一张盘，否则就把它安排到能容纳它的剩余容量最小的盘。
不知这个算法有无漏洞，反正是能够正确处理5楼的例子的。
欢迎大家批评指正。

FantasyDR

这个方法我最开始试验过...问题就是统计顶楼的32个数据的那组，还是统计成10张。
我在5楼的帖子，主要是为了说明下4楼的策略是有问题的。
这个其实还是贪心算法的一种，应该不是最优解吧？

现在就是在于顶楼那个32文件的，怎么才能统计成9张碟片？有些容量小的文件，也可以忽略不计，这样就剩下
0. 282.54
1. 415.87
2. 166.09
3. 168.35
4. 166.42
5. 172.73
6. 377.06
7. 181.03
8. 137.4
9. 383.14
10. 145.41
11. 154.97
12. 213.94
13. 188.46
14. 231.84
15. 334.81
16. 358.5
17. 397.8
18. 300.34
19. 381.53
20. 309.55
21. 278.73
22. 410.85
共23个数据了。

leesoft

呵呵。我不是也怀疑不是最优解么？
不过，还是给出一个明确的反例放心些。

FantasyDR

汗，还是把最优的统计结果发上来吧：
去掉了那些很小的文件，就是1mb左右的那些，小的不影响，因为总和不到10mb可以任意放在某个碟片的空余空间。剩下23个文件，手动排序得到9张碟片：

Disk1[683mb]3 files
383mb
154mb
145mb

Disk2[634mb]3 files
213mb
231mb
188mb

Disk3[693mb]2 files
334mb
358mb

Disk4[698mb]2 files
397mb
300mb

Disk5[691mb]2 files
381mb
309mb

Disk6[689mb]2 files
410mb
278mb

Disk7[698mb]2 files
415mb
282mb

Disk8[675mb]4 files
166mb
166mb
168mb
172mb

Disk9[695mb]3 files
377mb
181mb
137mb

如果用优先填满的贪心算法，则是10张碟片。

leesoft

呵呵。不用那么麻烦了。下面就是一个反例：
500 185 15
400 195 105

FantasyDR

嗯。上面是个反例，不过可以用jay的判断中值的方法求出最优解...
情况是比较复杂的。那个23个文件的例子，无论是比较中值，还是贪心算法，都不行……我是已经混乱了。

动态规划的算法，又要求有最优子条件，子条件找不到就白搭了。

leesoft

问题似乎可以这样“解决”：
从所有文件中找出总和最接近一张光盘容量的文件组合，刻盘。重复以上过程，直至无文件。
只是，“从所有文件中找出总和最接近一张光盘容量的文件组合”实现起来比较困难。当然可以用穷举法，不过，随着文件数的增加，将越来越耗时，以至无法在有限时间内完成。

my49cn

背包问题？以前上课就没听懂[em06]
很麻烦的说

FantasyDR

不是背包,比背包复杂一些.
貌似追求尽量添满一个碟片还是贪心算法,怀疑这样不能最优.尽量分散文件才可以...不知道了.越想越复杂...

qyfcool

先压缩,再分块......这个比较实用,如果你真想刻碟的话.......

116205035

无解？

Lendy

都想错了其实……
这个问题不是“能放就放，不能放就换”……
而是怎么放才能使每张光盘所剩的空间最少。
PS: 明天写一下，现在先睡觉 -_-bbb

FantasyDR

“每张光盘所剩的空间最少”……是无法判断的呀。贪心策略能保证某些光盘所剩的空间最少。
“每张剩余最少”如果理解为总剩余量最少，那么其实就是“所用光盘最少”的另外一种描述。

因为：剩余总量＝光盘数×光盘容量－文件总量
剩余总量和光盘数是同增减的，同时达到最大和最小。

Lendy

写了一个试验品，可以算出顶楼的最佳方案。
用这种思路写：怎么放才能使每张光盘所剩的空间最少。
不过不知道应该算什么方法，暂时称为“贪心+剪枝”……
没有经过任何优化。算32个数，可在瞬间完成；算64个数也是一闪而过；算128就慢慢等吧。。
先贴个EXE，程序继续优化。

Lendy

下面附两组实测数据：第一组是顶楼的数据；第二组是随便抽取的32个数（谁帮忙人工测算正误……）

1. 
   
2. ---=== Test 1 ===---
   
3. Disk space: 700
   
4. File No.1 size: 415.87
   
5. File No.2 size: 410.85
   
6. File No.3 size: 397.8
   
7. File No.4 size: 383.14
   
8. File No.5 size: 381.53
   
9. File No.6 size: 377.06
   
10. File No.7 size: 358.5
    
11. File No.8 size: 334.81
    
12. File No.9 size: 309.55
    
13. File No.10 size: 300.34
    
14. File No.11 size: 282.54
    
15. File No.12 size: 278.73
    
16. File No.13 size: 231.84
    
17. File No.14 size: 213.94
    
18. File No.15 size: 188.46
    
19. File No.16 size: 181.03
    
20. File No.17 size: 172.73
    
21. File No.18 size: 168.35
    
22. File No.19 size: 166.42
    
23. File No.20 size: 166.09
    
24. File No.21 size: 154.97
    
25. File No.22 size: 145.41
    
26. File No.23 size: 137.4
    
27. File No.24 size: 1.07
    
28. File No.25 size: 0.83
    
29. File No.26 size: 0.3
    
30. File No.27 size: 0.01
    
31. File No.28 size: 0.01
    
32. File No.29 size: 0.01
    
33. File No.30 size: 0.01
    
34. File No.31 size: 0.01
    
35. File No.32 size: 0
    
36. File No.33 size: -1
    
37. 
    
38. Disk No.1:
    
39.   415.87  145.41  137.4  0.83  0.3  0.01  0.01  0.01  0.01  0.01
    
40.   (Total: 11 files, 699.86MB)
    
41. Disk No.2:
    
42.   410.85  282.54  1.07
    
43.   (Total: 3 files, 694.46MB)
    
44. Disk No.3:
    
45.   397.8  300.34
    
46.   (Total: 2 files, 698.14MB)
    
47. Disk No.4:
    
48.   383.14  309.55
    
49.   (Total: 2 files, 692.69MB)
    
50. Disk No.5:
    
51.   381.53  278.73
    
52.   (Total: 2 files, 660.26MB)
    
53. Disk No.6:
    
54.   377.06  166.42  154.97
    
55.   (Total: 3 files, 698.45MB)
    
56. Disk No.7:
    
57.   358.5  172.73  168.35
    
58.   (Total: 3 files, 699.58MB)
    
59. Disk No.8:
    
60.   334.81  188.46  166.09
    
61.   (Total: 3 files, 689.36MB)
    
62. Disk No.9:
    
63.   231.84  213.94  181.03
    
64.   (Total: 3 files, 626.81MB)
    
65. 
    
66. 
    
67. ---=== Test 2 ===---
    
68. Disk space: 700
    
69. File No.1 size: 123.42
    
70. File No.2 size: 435.23
    
71. File No.3 size: 324.12
    
72. File No.4 size: 32.41
    
73. File No.5 size: 514.10
    
74. File No.6 size: 122.98
    
75. File No.7 size: 52.31
    
76. File No.8 size: 23.98
    
77. File No.9 size: 74.10
    
78. File No.10 size: 243.49
    
79. File No.11 size: 587.20
    
80. File No.12 size: 483.10
    
81. File No.13 size: 0.9
    
82. File No.14 size: 10.23
    
83. File No.15 size: 0.24
    
84. File No.16 size: 1.23
    
85. File No.17 size: 98.53
    
86. File No.18 size: 76.42
    
87. File No.19 size: 6.43
    
88. File No.20 size: 78.10
    
89. File No.21 size: 93.12
    
90. File No.22 size: 423.54
    
91. File No.23 size: 671.10
    
92. File No.24 size: 20.49
    
93. File No.25 size: 93.10
    
94. File No.26 size: 200.10
    
95. File No.27 size: 129.31
    
96. File No.28 size: 90.1
    
97. File No.29 size: 72.10
    
98. File No.30 size: 32.46
    
99. File No.31 size: 5.23
    
100. File No.32 size: 6.10
     
101. File No.33 size: -1
     
102. 
     
103. Disk No.1:
     
104.   671.1  10.23  6.43  6.1  5.23  0.9
     
105.   (Total: 6 files, 699.99MB)
     
106. Disk No.2:
     
107.   587.2  90.1  20.49  1.23  0.24
     
108.   (Total: 5 files, 699.26MB)
     
109. Disk No.3:
     
110.   514.1  129.31  32.46  23.98
     
111.   (Total: 4 files, 699.85MB)
     
112. Disk No.4:
     
113.   483.1  123.42  93.12
     
114.   (Total: 3 files, 699.64MB)
     
115. Disk No.5:
     
116.   435.23  98.53  93.1  72.1
     
117.   (Total: 4 files, 698.96MB)
     
118. Disk No.6:
     
119.   423.54  243.49  32.41
     
120.   (Total: 3 files, 699.44MB)
     
121. Disk No.7:
     
122.   324.12  200.1  122.98  52.31
     
123.   (Total: 4 files, 699.51MB)
     
124. Disk No.8:
     
125.   78.1  76.42  74.1
     
126.   (Total: 3 files, 228.62MB)
     

复制代码