如果有人可以帮助改善运行时，那就太好了！
我有一辆最大容量为C的卡车，初始存货为S1。卡车经过固定路线仓库-> 1-> 2-> ...-> N-1-> N->仓库
每个工位i = 1…n的当前库存量为Xi，目标库存量为Xi *。在每个工位，卡车可以根据情况决定下车或取下可能的物品数量。设Yi为卡车到访i站后剩余的物品数。总成本为TC（按代码编写）。
我实现了一个动态的编程代码，其中xd是每个站点上取下的单位数，s是卡车上的物品数：
在-min（c-s，xi）这是代码-问题是它运行了好几天，没有返回答案。
有谁知道更好地实现它的方法？
n = 50
c=10
s1 = 6
xi = [59,33,14,17,26,31,91,68,3,53,53,73,86,24,98,37,55,14,97,61,57,23,65,24,50,31,39,31,24,60,92,80,48,28,47,81,19,82,3,74,50,89,86,37,98,11,12,94,6,61]
x_star = [35,85,51,88,44,20,79,68,97,7,68,19,50,19,42,45,8,9,61,60,80,4,96,57,100,22,2,51,56,100,6,84,96,69,18,31,86,6,39,6,78,73,14,45,100,43,89,4,76,70]
c_plus = [4.6,1.3,2.7,0.5,2.7,5,2.7,2.6,4.1,4,3.2,3.1,4.8,3.1,0.8,1,0.5,5,5,4.6,2.5,4.1,2.1,2.9,1.4,3.9,0.5,1.7,4.9,0.6,2.8,4.9,3.3,4.7,3.6,2.4,3.4,1.5,1.2,0.5,4.3,4.3,3.9,4.8,1.2,4.8,2,2.2,5,4.5]
c_minus = [8.7,7.5,11.7,6.9,11.7,14.4,7.5,11.1,1.2,1.5,12,8.1,2.7,8.7,9.3,1.5,0.3,1.5,1.2,12.3,5.7,0.6,8.7,8.1,0.6,3.9,0.3,5.4,14.7,0,10.8,6.6,8.4,9.9,14.7,2.7,1.2,10.5,9.3,14.7,11.4,5.4,6,13.2,3.6,7.2,3,4.8,9,8.1]
dict={}
values={}
def tc(i,xd):
yi = xi[i-1] + xd
if yi>=x_star[i-1]:
tc = c_plus[i-1]*(yi-x_star[i-1])
else:
tc = c_minus[i-1]*(x_star[i-1]-yi)
return tc
def func(i,s):
if i==n+1:
return 0
else:
a=[]
b=[]
start = min(c-s,xi[i-1])*-1
for xd in range(start,s+1):
cost = tc(i,xd)
f= func(i+1,s-xd)
a.append(cost+f)
b.append(xd)
min_cost = min(a)
index = a.index(min_cost)
xd_optimal = b[index]
if i in values:
if values[i]>min_cost:
dict[i] = xd_optimal
values[i] = min_cost
else:
values[i] = min_cost
dict[i] = xd_optimal
return min_cost
best_cost = func(1,s1)
print best_cost
print dict
最佳答案
一，解决方案：
通常使用完全相同的参数来调用该函数。因此，我添加了一个缓存，该缓存可以避免重复计算重复出现的参数集。这几乎在我的计算机上立即返回答案。
cache = {}
def func(i,s):
if i==n+1:
return 0
else:
try:
return cache[(i,s)]
except KeyError:
pass
a=[]
...
cache[(i,s)] = min_cost
return min_cost
这就是我发现该怎么做的方法...
我修改了代码以产生一些调试输出：
...
count = 0
def func(i,s):
global count
count += 1
print count, ':', i, s
...
将n设置为2将产生以下输出：
1 : 1 6
2 : 2 10
3 : 3 10
4 : 3 9
5 : 3 8
6 : 3 7
7 : 3 6
8 : 3 5
9 : 3 4
10 : 3 3
11 : 3 2
12 : 3 1
13 : 3 0
14 : 2 9
15 : 3 10
16 : 3 9
17 : 3 8
18 : 3 7
19 : 3 6
20 : 3 5
21 : 3 4
22 : 3 3
23 : 3 2
24 : 3 1
25 : 3 0
26 : 2 8
27 : 3 10
28 : 3 9
29 : 3 8
30 : 3 7
31 : 3 6
32 : 3 5
...
您会注意到，经常使用相同的参数集调用该函数。
在（i = 2，s = 10）之后，它将运行（i = 3，s = x）的所有组合。在（i = 2，s = 9）之后再次执行此操作。 133次递归后，整个过程完成。设置n = 3需要1464次递归，设置n = 4需要16105次递归。您可以看到导致...
备注：我完全不知道您的优化如何工作。相反，我只是简单地对待症状:)