翻箱问题（最短路径问题）数学建模
翻箱问题 最短路径问题
Python数学建模
不用编程问个解题思路需要用的算法啥的
最极端的情况就是箱子的进出顺序完全一致，这种情况下比较合理的放置方式可能是
3 6 9 12
2 5 8 11 17 18 19 20
1 4 7 10 13 14 15 16
翻箱数12，操作数22
以这个形式为结果推导放入规则：
1、按箱子数和R、C的值计算取出编号最佳位置，也就是最大的C个数在底层，接下来的C个数在倒数第二层，以此类推，最小的数在最顶层，这样翻箱数为0，操作数为箱子的总数，顺序类似这样
1 2 3 4
5 6 7 8 9 10 11 12
13 14 15 16 17 18 19 20
这样可以确定底层，中层，顶层的编号
2、箱子放入时，设定以下规则，
2.1、顶层编号的箱子尽可能往高层放，如非必要，不放到最底层
2.2、中层编号的箱子尽可能往中层放，如非必要，不放到最底层和最顶层，没有中层可选的情况下放入顶层
2.3、底层编号的箱子尽可能的放入底层，没有底层的情况下放中层，中底层都没有的情况下放顶层
2.4、每个箱子放入时，如果有多个位置可选时，优先选择下一层数字比自己大的位置放
在这个原则下，例子中的箱子放入后的位置如图，取出时翻箱数为0，操作数20
按照这个思路给个编程解决方案：
import numpy as np
def in_box(places, n):
global top,mid,bot
if n in top:
lens = [len(p) if len(p)<3 else -1 for p in places]
max_len_index = np.where(np.array(lens)==max(lens))[0].tolist()
for mi in max_len_index:
if len(places[mi])==0 or places[mi][-1]>n:
places[mi].append(n)
break
else:
places[max_len_index[0]].append(n)
elif n in mid:
lens = [len(p) if len(p)<3 else -1 for p in places]
max_len_index = np.where(np.array(lens)==1)[0].tolist()
if len(max_len_index)==0:
max_len_index = np.where(np.array(lens)==max(lens))[0].tolist()
for mi in max_len_index:
if len(places[mi])==0 or places[mi][-1]>n:
places[mi].append(n)
break
else:
places[max_len_index[0]].append(n)
else:
lens = [len(p) for p in places]
min_len_index = np.where(np.array(lens)==min(lens))[0].tolist()
for mi in min_len_index:
if len(places[mi])==0 or places[mi][-1]>n:
places[mi].append(n)
break
else:
places[min_len_index[0]].append(n)
return places
boxes = [[1,18], [2,14],[3,13], [4,10], [5,9],
[6,20], [7,12],[8,1], [9,5], [10,3],
[11,6], [12,2],[13,17],[14,15],[15,8],
[16,19],[17,4],[18,11],[19,7],[20,16]]
# boxes = [[i,i] for i in range(1,21)]
R = 3
C = 8
places = [[] for i in range(C)]
total = len(boxes)
outNumbers = [(i+1) for i in range(total)]
top = outNumbers[:total%C]
mid = outNumbers[total%C:total%C+C]
bot = outNumbers[total%C+C:]
for box in boxes:
outNo = box[1]
places = in_box(places, outNo)
for i in range(C):
p = places[i]
while len(p)<R:
p.append('')
p.reverse()
for i in range(R):
for j in range(C):
print(f'{places[j][i]:<8}',end=' ')
print()
利用题主给的例子和极端情况为例，箱子放入之后的顺序分别是：
题主的例子翻箱数为0，操作数20，极端情况为翻箱数12，操作数32