1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
| from math import exp
from matplotlib.colors import CSS4_COLORS
from matplotlib.pyplot import figure, show
from mpl_toolkits.mplot3d.art3d import Poly3DCollection
from numpy import array, concatenate, repeat
from random import random, sample, shuffle
available_points = {}
putted_items = []
x_reference, z_reference, box_length, box_width, box_height, x, y, z = 0, 0, 0, 0, 0, 0, 0, 0
def isRoomEnough(item1, position):
if item1[0] + position[0] <= box_length and item1[1] + position[1] <= box_width and item1[2] + position[2] <= box_height:
for item2 in putted_items:
if item2['position'] == position:
return False
overlap = 0
if item2['position'][0] < item1[0] + position[0] and position[0] < item2['position'][0] + item2['volume'][0] and item2['position'][1] < item1[1] + position[1] and position[1] < item2['position'][1] + item2['volume'][1]:
overlap = 1
if item2['position'][0] < item1[0] + position[0] and position[0] < item2['position'][0] + item2['volume'][0] and item2['position'][2] < item1[2] + position[2] and position[2] < item2['position'][2] + item2['volume'][2]:
overlap += 1
if item2['position'][1] < item1[1] + position[1] and position[1] < item2['position'][1] + item2['volume'][1] and item2['position'][2] < item1[2] + position[2] and position[2] < item2['position'][2] + item2['volume'][2]:
overlap += 1
if overlap > 1:
return False
return True
def isInnerReference(item):
global x, y, z
for position in available_points:
if item[0] + position[0] <= x_reference and item[2] + position[2] <= z_reference and isRoomEnough(item, position) == True:
x, y, z = position[0], position[1], position[2]
return True
def expandReference(item):
global x_reference, z_reference, x, y, z
if x_reference == 0 or x_reference == box_length:
if isRoomEnough(item, (0, 0, z_reference)) == True:
x, y, z, x_reference = 0, 0, z_reference, item[0]
z_reference += item[2]
return True
elif z_reference < box_height:
x_reference, z_reference = box_length, box_height
return isInnerReference(item) or expandReference(item)
else:
for position in available_points:
if position[0] == x_reference and position[1] == 0 and item[2] + position[2] <= z_reference and isRoomEnough(item, position) == True:
x, y, z = position[0], position[1], position[2]
x_reference += item[0]
return True
x_reference = box_length
return isInnerReference(item) or expandReference(item)
def pack(items):
global available_points, putted_items, x_reference, z_reference
available_points = {(0, 0, 0)}
positions = []
putted_items = []
sizes = []
item_volume = x_reference = z_reference = 0
for item in items:
if (isInnerReference(item) or expandReference(item)) and isRoomEnough(item, (x, y, z)):
putted_items.append({
'position': (x, y, z),
'volume': item,
})
available_points.remove((x, y, z))
available_points.add(((x + item[0], y, z)))
available_points.add(((x, y + item[1], z)))
available_points.add(((x, y, z + item[2])))
positions.append((x, y, z))
sizes.append(item)
item_volume += item[0] * item[1] * item[2]
'''print('有一个长', item[0], '宽', item[1], '高', item[2], '的物品成功放置于', (x, y, z))
else:
print('有一个长', item[0], '宽', item[1], '高', item[2], '的物品放置失败')'''
return item_volume / box_length / box_width / box_height, positions, sizes
def read():
try:
box_length, box_width, box_height = map(int, input('请依次输入箱子的长、宽、高(整数),以空格分隔:').split())
if box_length > 0 and box_width > 0 and box_height > 0:
return box_length, box_width, box_height
else:
print('输入了非正数')
except ValueError:
print('输入的不是三个数')
return read()
while True:
items = []
items_kind = 0
box_length, box_width, box_height = read()
while True:
try:
items_length, items_width, items_height, number = map(int, (input('请依次输入物品的长、宽、高、个数(整数),以空格分隔。每行一组物品。若输入完毕请输入Ctrl+Z并回车:').split()))
if items_length > 0 and items_width > 0 and items_height > 0 and number > 0:
item = tuple(sorted((items_length, items_width, items_height), reverse=True))
for i in range(number):
items.append(item)
items_kind += 1
else:
print('输入了非正数')
except EOFError:
break
except ValueError:
print('输入的不是四个数')
items.sort(key=lambda item: item[0] * item[1] * item[2], reverse=True)
filling_rate, positions, sizes = pack(items)
print('0 次退火填充率:', filling_rate, '放置数量:', len(sizes))
best_items, best_positions, best_sizes, max_filling_rate = items, positions, sizes, filling_rate
for i in range(2):
temperature, area_length = 0.92, items_kind
while temperature >= 0.01:
for j in range(area_length):
new_items = items
for k, item in enumerate(new_items):
l = list(item)
shuffle(l)
new_items[k] = tuple(l)
shuffle(new_items)
new_filling_rate, new_positions, new_sizes = pack(new_items)
if new_filling_rate > filling_rate or exp((new_filling_rate - filling_rate) * 10 / temperature) > random():
filling_rate, items, positions, sizes = new_filling_rate, new_items, new_positions, new_sizes
if new_filling_rate > max_filling_rate:
max_filling_rate, best_items, best_positions, best_sizes = new_filling_rate, new_items, new_positions, new_sizes
area_length += items_kind
temperature *= 0.92
print(i + 1, '次退火填充率:', max_filling_rate, '放置数量:', len(best_sizes))
item_number = len(best_sizes)
if item_number > 0:
subplot = figure().add_subplot(projection='3d')
subplot.set_box_aspect((box_length, box_width, box_height))
arr = []
for position, size in zip(positions, sizes):
a = array([[[0, 1, 0], [0, 0, 0], [1, 0, 0], [1, 1, 0]], [[0, 0, 0], [0, 0, 1], [1, 0, 1], [1, 0, 0]], [[1, 0, 1], [1, 0, 0], [1, 1, 0], [1, 1, 1]], [[0, 0, 1], [0, 0, 0], [0, 1, 0], [0, 1, 1]], [[0, 1, 0], [0, 1, 1], [1, 1, 1], [1, 1, 0]], [[0, 1, 1], [0, 0, 1], [1, 0, 1], [1, 1, 1]]]).astype(float)
for i in range(3):
a[:, :, i] *= size[i]
arr.append(a + array(position))
subplot.add_collection3d(Poly3DCollection(concatenate(arr), edgecolor='k', facecolors=repeat(sample(CSS4_COLORS.keys(), item_number), 6)))
subplot.set_xlim([0, box_length])
subplot.set_ylim([0, box_width])
subplot.set_zlim([0, box_height])
show()
|
