削减成本算法优化
我有一张木板，并在木板上给出了N个标记。现在我必须切割木板上的所有标记，以便将所有标记切割成最小值。现在假设我先切割了i那么成本通过使用两个作为输入的乘数a和b给出，并且成本是a *（左）+ b *（右），其中左和右是切割后木材的剩余部分的尺寸。例如如果我有一个长度为10，a = 3和b = 4的木头，并且如果我有前面的标记列表：[1,3,5,7,10]，所以我不能砍掉第一个和最后一个标记，因为它们是开始和所以假设如果我先从7开始，那么切割的成本将是3 *（7-1）+ 4 *（10-7）= 18 + 12 = 30，现在我所拥有的木材是一个以标记1开始标记7，另一个开始标记7以结束木头广告我会重复这个过程，直到所有的标记都被切掉。削减成本算法优化
现在读到这个问题后，我立即想到，为了以最低成本砍伐木材，我首先需要找到中点（切割点的中位数），在那里我应该砍木头并重复这个过程一次又一次，直到木材没有剩余的切割点，但我在解决切割后获得的合适木材时遇到问题
样品输入：切割有[1,3,5,9,16,22]的木材会有最低成本= 163当我们第一次以中位数9开始时，我们现在会先用木头[1,3,5,9]和[9,16,22]来解决我们将要得到的左木[1,3,5 ] [5,9]，现在再次切割我们有[1,3] [3,5] [5,9]和现在剩下的[9,16,22]现在操作这种木材，我们已经切割了所有商标和名单将是[1,3] [3,5] [5,9] [9,16] [16,22]并在此操作的成本将是最低
这里是我的代码：
for _ in range(int(input())): #no of test cases
a,b=map(int,input().split()) #multiplier element of cost ex: 3,4
n=int(input()) #total number of cuts ex: 6
x=list(map(int,input().split())) #where the cuts are the wood ex:
#[1,3,5,9,16,22]
lis=[]
cost=0
average=sum(x)/len(x)
median=min(x,key=lambda X:abs(X-average)) #calculated the median
cost+=a*(median-x[0])+b*(x[-1]-median) #calculated the cost of cutting
print(cost)
var=x.index(median) #found the index of median
x_left=x[:var+1] #split the wood in left and right
x_right=x[var:]
lis.append(x_right)
while(len(x_left)>2): #done the same process going first on left wood
average=sum(x_left)/len(x_left)
median=min(x_left,key=lambda X:abs(X-average))
cost+=a*(median-x_left[0])+b*(x_left[-1]-median)
var=x.index(median)
x_left=x_left[:var+1]
x_right=x_left[var:] #this wood would again have right component so
#stored that right side in list named lis
lis.append(x_right)
print(cost) #fully solved by moving leftwards
print(lis)
tt=len(lis)
for i in lis: #but the problem start here i have all the right
#pieces of wood that i had stored in lis but now i
#can't evaluate them
if(len(i)<3):
lis.pop(lis.index(i))
else:
continue
print(lis)
while(tt!=0):
xx=lis.pop(0)
ttt=len(xx)
if(ttt>2):
average=sum(xx)/ttt
median=min(xx,key=lambda X:abs(X-average))
cost+=a*(median-xx[0])+b*(xx[-1]-median)
var=x.index(median)
x_left=xx[:var+1]
x_right=xx[var:]
if(len(x_left)>2):
lis.append(x_left)
if(len(x_right)>2):
lis.append(x_right)
print(cost)
首先，这是一个递归生成器solve_gen，它检查所有可能的切割顺序，然后选择最小的一个。尽管代码很紧凑，并且如果标记数量很小，则代码运行正常，但随着标记数量的增加，它很快就会变得效率低下。我还包含了一个功能apply_cuts，它将一系列剪切应用于标记序列，以便您可以看到剪切以该顺序发生。
solve_gen使用全球count来跟踪所做的递归调用的数量。对于算法的操作而言，count不是必需的，但它给了我们一个指示该功能在做多少工作的指示。
def cost(seq, m):
return (seq[-1] - seq[0]) * m
def solve_gen(seq):
global count
count += 1
if len(seq) == 2:
yield 0,()
return
for i in range(1, len(seq)-1):
left, x, right = seq[:i+1], seq[i], seq[i:]
val = cost(left, a) + cost(right, b)
for lval, lcuts in solve_gen(left):
for rval, rcuts in solve_gen(right):
yield (val + lval + rval, (x,) + lcuts + rcuts)
def apply_cuts(seq, cuts):
total = 0
old = [seq]
for x in cuts:
new = []
for u in old:
if x in u:
i = u.index(x)
left, right = u[:i+1], u[i:]
val = cost(left, a) + cost(right, b)
new.extend((left, right))
else:
new.append(u)
print(x, new, val)
total += val
old = new[:]
return total
# Test
# Recursion counter
count = 0
a, b = 3, 4
seq = (1, 3, 5, 9, 16, 22)
print(seq)
results = list(solve_gen(seq))
val, cuts = min(results)
print('Cost: {}, Cuts: {}'.format(val, cuts))
print('Results length: {}, Count: {}'.format(len(results), count))
print('\nCutting sequence')
print(apply_cuts(seq, cuts))
输出
(1, 3, 5, 9, 16, 22)
Cost: 163, Cuts: (9, 5, 3, 16)
Results length: 14, Count: 90
Cutting sequence
9 [(1, 3, 5, 9), (9, 16, 22)] 76
5 [(1, 3, 5), (5, 9), (9, 16, 22)] 28
3 [(1, 3), (3, 5), (5, 9), (9, 16, 22)] 14
16 [(1, 3), (3, 5), (5, 9), (9, 16), (16, 22)] 45
163
FWIW，这里有相同a & b用较长标记序列的结果。
(1, 3, 5, 9, 16, 22, 31, 33, 35, 39, 46)
Cost: 497, Cuts: (31, 16, 9, 5, 3, 22, 39, 35, 33)
Results length: 4862, Count: 41990
我们可以通过在递归的每个阶段找到极小，而不是寻找最小的一切准备这更有效。然而，由于算法研究各种切割选项，它经常重复之前完成的计算。所以我们可以通过使用缓存来使代码更加高效，即我们将以前的结果存储在字典中，所以如果我们需要再次进行相同的剪切，我们可以在缓存中查找它，而不是重新计算它。
我们可以编写我们自己的缓存，但functools模块提供了lru_cache，它可以用作装饰器。我们也可以给cost函数一个缓存，尽管它的计算相当简单，所以缓存可能不会节省很多时间。 lru_cache的一个很好的特性是它还可以提供缓存统计信息，这让我们知道缓存的有用性。
from functools import lru_cache
@lru_cache(None)
def cost(seq, m):
return (seq[-1] - seq[0]) * m
@lru_cache(None)
def solve(seq):
global count
count += 1
if len(seq) == 2:
return 0,()
results = []
for i in range(1, len(seq)-1):
left, x, right = seq[:i+1], seq[i], seq[i:]
val = cost(left, a) + cost(right, b)
lval, lcuts = solve(left)
rval, rcuts = solve(right)
results.append((val + lval + rval, (x,) + lcuts + rcuts))
return min(results)
# Test
# Recursion counter
count = 0
a, b = 3, 4
seq = (1, 3, 5, 9, 16, 22)
print(seq)
val, cuts = solve(seq)
print('Cost: {}, Cuts: {}'.format(val, cuts))
print('Count: {}\n'.format(count))
print('cost cache', cost.cache_info())
print('solve cache', solve.cache_info())
输出
(1, 3, 5, 9, 16, 22)
Cost: 163, Cuts: (9, 5, 3, 16)
Count: 15
cost cache CacheInfo(hits=20, misses=20, maxsize=None, currsize=20)
solve cache CacheInfo(hits=26, misses=15, maxsize=None, currsize=15)
幸运的是，我们像以前一样得到同样的结果。 ;）注意，递归计数现在要低得多。让我们用更长的标记序列来尝试。
(1, 3, 5, 9, 16, 22, 31, 33, 35, 39, 46)
Cost: 497, Cuts: (31, 16, 9, 5, 3, 22, 39, 35, 33)
Count: 55
cost cache CacheInfo(hits=240, misses=90, maxsize=None, currsize=90)
solve cache CacheInfo(hits=276, misses=55, maxsize=None, currsize=55)
与先前的41990相比，递归计数仅为55;显着减少。我们可以看到这些缓存已被广泛使用。
FWIW，所有可能的切割序列的数量是由Catalan numbers这往往在组合问题突然出现给出。
非常感谢！我的三个问题都已经被你回答了。你是救星:) – Demonking28
@ Demonking28我的荣幸！你很幸运，我喜欢组合问题。 ;） –
def cost（seq，m）： return（seq [-1] - seq [0]）* m这里'm'是什么？ – uitwaa
这个问题，需要的功能和递归。你想要的是这样的：
function total_cost(a, b, marks):
# Do something clever here
现在你有不到3分，问题很简单。不需要削减和成本为0
function total_cost(a, b, marks):
if len(marks) < 3:
return 0
else
# Do something clever here
如果你有2个以上的痕迹，在任何特定的地方切割的成本削减那里的成本，再加上切割剩余的费用。因此，切割成本是最低或成本。这应该足以填补巧妙的东西。
此解决方案将缓慢运行，并有许多削减。要解决这个问题，你应该查找“memoization”。
这是编码竞赛的问题吗？你能否提供一个原始问题的链接？ –
您的代码相当混乱，并且在开始时它没有正确缩进。但是，将硬编码数据替换为从'输入'读取数据的起始部分会更好，当您尝试开发代码时，在输入提示处输入数据会很烦人。你可以减少你的代码的混乱，并通过使用函数减少重复。你为什么认为中位数的减少会起作用？它可能在某些情况下，但一般情况下不会。切入点计算_需要考虑'a'和'b'。 –
@ PM2Ring，因为如果木头沿着一端被切割，其余的将会有较大的尺寸并且成本会更大。假设我有长度为20的木材并且在其上标记[1,3,5,7,10 ，15,17,20]现在假设我有同样的a和b，那么我可以降低成本的最佳方式是选择10，因为左端和右端的差异将是相同的，如果我将减少15分首先削减的成本将是相同的，其余的成本将会更高。 – Demonking28