老师测试的时候是用100个物体来装箱,很容易就Out of memory……
所以一般的烂算法是混不关的。这个老师巨可恶,自己本事不大,把作业和考试弄的很难。
我当然是学计算机专业的,不然怎么会碰上这个问题我们这学期已经算幸运了,上学期他们写的作业是大厦里电梯上下运送货物的优化问题,而且要求是多线程的
所以一般的烂算法是混不关的。这个老师巨可恶,自己本事不大,把作业和考试弄的很难。
我当然是学计算机专业的,不然怎么会碰上这个问题我们这学期已经算幸运了,上学期他们写的作业是大厦里电梯上下运送货物的优化问题,而且要求是多线程的
第一个方法不排序,直接装箱,速度比较快
第二个方法先从大到小排序,再装箱,速度稍微慢了一点,但是箱子用的更少,相对来说每个箱子也装的更满。下面的是我的测试结果,各装100个物体(随机),重复1000次,然取所需时间的平均值。
每一行的第一个值是箱子剩下的可装的重量,第二个是已经被填充的重量,第三个是填充物体的数量,最后那些扩号里面的是所装的物体。物体分两部分,第一部分是序列号,第二部分是物体重量。Using strategy1 (run 1000 times):
Start time = 90ms
End time = 2294ms
Average time for strategy1: 2.204msTotal amount of boxes used: 56
The list of boxes is:
0.0 1.0 2 (17, 0.68) (20, 0.32)
0.0 1.0 1 (86, 1.0)
0.0 1.0 2 (24, 0.68) (26, 0.32)
0.0 1.0 2 (27, 0.54) (31, 0.46)
0.0 1.0 2 (36, 0.9) (51, 0.1)
0.0 1.0 3 (63, 0.44) (66, 0.41) (75, 0.15)
0.0 1.0 2 (34, 0.67) (85, 0.33)
0.0 1.0 3 (87, 0.78) (88, 0.18) (89, 0.04)
0.0 1.0 3 (22, 0.7) (61, 0.29) (65, 0.01)
0.01 0.99 1 (91, 0.99)
0.01 0.99 1 (4, 0.99)
0.01 0.99 2 (10, 0.4) (13, 0.59)
0.01 0.99 1 (79, 0.99)
0.01 0.99 2 (0, 0.85) (25, 0.14)
0.01 0.99 1 (73, 0.99)
0.01 0.99 1 (37, 0.99)
0.01 0.99 3 (11, 0.63) (18, 0.33) (42, 0.03)
0.02 0.98 1 (41, 0.98)
0.02 0.98 2 (38, 0.95) (48, 0.03)
0.02 0.98 2 (21, 0.84) (46, 0.14)
0.02 0.98 2 (53, 0.8) (55, 0.18)
0.02 0.98 2 (58, 0.81) (64, 0.17)
0.02 0.98 2 (49, 0.57) (56, 0.41)
0.02 0.98 2 (69, 0.61) (74, 0.37)
0.03 0.97 2 (67, 0.59) (90, 0.38)
0.03 0.97 2 (47, 0.58) (50, 0.39)
0.03 0.97 2 (44, 0.62) (59, 0.35)
0.03 0.97 2 (82, 0.73) (99, 0.24)
0.04 0.96 2 (83, 0.74) (84, 0.22)
0.04 0.96 1 (93, 0.96)
0.04 0.96 2 (30, 0.7) (62, 0.26)
0.06 0.94 2 (5, 0.64) (6, 0.3)
0.06 0.94 2 (57, 0.75) (70, 0.19)
0.06 0.94 2 (12, 0.65) (15, 0.29)
0.06 0.94 2 (7, 0.37) (9, 0.57)
0.06 0.94 2 (39, 0.75) (40, 0.19)
0.08 0.92 2 (28, 0.72) (33, 0.2)
0.08 0.92 2 (81, 0.54) (92, 0.38)
0.08 0.92 1 (29, 0.92)
0.08 0.92 2 (23, 0.61) (32, 0.31)
0.09 0.91 2 (8, 0.75) (16, 0.16)
0.09 0.91 3 (1, 0.25) (2, 0.28) (3, 0.38)
0.09 0.91 2 (96, 0.44) (98, 0.47)
0.09 0.91 2 (45, 0.46) (54, 0.45)
0.1 0.9 1 (14, 0.9)
0.11 0.89 2 (76, 0.68) (78, 0.21)
0.11 0.89 2 (19, 0.71) (43, 0.18)
0.13 0.87 1 (60, 0.87)
0.13 0.87 2 (35, 0.7) (52, 0.17)
0.14 0.86 2 (71, 0.44) (77, 0.42)
0.16 0.84 1 (68, 0.84)
0.18 0.82 1 (94, 0.82)
0.36 0.64 1 (80, 0.64)
0.36 0.64 1 (72, 0.64)
0.38 0.62 1 (95, 0.62)
0.39 0.61 1 (97, 0.61)
Using strategy2 (run 1000 times):
Start time = 30ms
End time = 3004ms
Time used to sort: 40ms
Average time for strategy2: 2.934msTotal amount of boxes used: 54
The list of boxes is:
0.0 1.0 1 (86, 1.0)
0.0 1.0 2 (87, 0.78) (84, 0.22)
0.0 1.0 2 (83, 0.74) (62, 0.26)
0.0 1.0 3 (72, 0.64) (85, 0.33) (42, 0.03)
0.0 1.0 2 (21, 0.84) (16, 0.16)
0.0 1.0 2 (8, 0.75) (1, 0.25)
0.0 1.0 2 (94, 0.82) (43, 0.18)
0.0 1.0 2 (73, 0.99) (65, 0.01)
0.0 1.0 3 (9, 0.57) (10, 0.4) (48, 0.03)
0.0 1.0 3 (39, 0.75) (78, 0.21) (89, 0.04)
0.0 1.0 2 (95, 0.62) (90, 0.38)
0.0 1.0 2 (58, 0.81) (40, 0.19)
0.0 1.0 2 (67, 0.59) (56, 0.41)
0.0 1.0 2 (28, 0.72) (2, 0.28)
0.0 1.0 2 (17, 0.68) (20, 0.32)
0.0 1.0 2 (36, 0.9) (51, 0.1)
0.0 1.0 2 (69, 0.61) (50, 0.39)
0.0 1.0 2 (30, 0.7) (6, 0.3)
0.0 1.0 2 (76, 0.68) (26, 0.32)
0.0 1.0 2 (27, 0.54) (45, 0.46)
0.0 1.0 2 (47, 0.58) (77, 0.42)
0.0 1.0 2 (53, 0.8) (33, 0.2)
0.0 1.0 2 (12, 0.65) (59, 0.35)
0.0 1.0 2 (44, 0.62) (3, 0.38)
0.0 1.0 2 (11, 0.63) (7, 0.37)
0.0 1.0 2 (19, 0.71) (15, 0.29)
0.0 1.0 2 (0, 0.85) (75, 0.15)
0.0 1.0 2 (34, 0.67) (18, 0.33)
0.0 1.0 2 (81, 0.54) (31, 0.46)
0.0 1.0 2 (13, 0.59) (66, 0.41)
0.01 0.99 3 (5, 0.64) (88, 0.18) (52, 0.17)
0.01 0.99 2 (97, 0.61) (92, 0.38)
0.01 0.99 2 (22, 0.7) (61, 0.29)
0.01 0.99 1 (79, 0.99)
0.01 0.99 1 (37, 0.99)
0.01 0.99 1 (91, 0.99)
0.01 0.99 1 (4, 0.99)
0.01 0.99 2 (24, 0.68) (32, 0.31)
0.01 0.99 2 (57, 0.75) (99, 0.24)
0.02 0.98 2 (68, 0.84) (25, 0.14)
0.02 0.98 2 (23, 0.61) (74, 0.37)
0.02 0.98 1 (41, 0.98)
0.04 0.96 1 (93, 0.96)
0.05 0.95 1 (38, 0.95)
0.05 0.95 3 (80, 0.64) (64, 0.17) (46, 0.14)
0.08 0.92 2 (82, 0.73) (70, 0.19)
0.08 0.92 2 (98, 0.47) (54, 0.45)
0.08 0.92 1 (29, 0.92)
0.1 0.9 1 (14, 0.9)
0.12 0.88 2 (35, 0.7) (55, 0.18)
0.12 0.88 2 (63, 0.44) (71, 0.44)
0.13 0.87 1 (60, 0.87)
0.43 0.57 1 (49, 0.57)
0.56 0.44 1 (96, 0.44)Press any key to continue...