削减成本算法优化

Question

我有一张木板，并在木板上给出了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) 

Answer 1

首先，这是一个递归生成器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这往往在组合问题突然出现给出。

Answer 2

这个问题，需要的功能和递归。你想要的是这样的：

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”。