切削成本算法优化

Question

我有一个木片，并在木材sheet.Now上做了N个标记，我必须在木材上切下所有的标记，这样在minimum.Now中切割所有标记的成本，假设我首先切割I标记，然后通过两个乘数a和b给出成本，而成本是a*(左)+b*(右)，其中左和右是切割.for后剩下的木材的大小，例如，如果我有一个10和a=3和b=4的木材，如果我有ex的标记列表: 1,3,5,7，，所以我不能第一个和最后一个标记，因为它们是木材的起点和终点，所以假设我首先从标记7开始，那么切割的成本将是3*(7-1)+4*(10-7)=18+12=30，现在我要的木材是从标记1开始到标记7的木材，另一个是7标记到木材广告末尾的木材，我会重复这个过程，直到所有的标记都被切割为止。

现在，在阅读了这个问题后，我立刻想到，为了把木材的成本降到最低，我首先需要找到中点(切点的中间值)，在那里，我应该一次又一次地重复这个过程，直到木材没有切割点为止，但我在解决切割后获得的正确木材时遇到了问题。

样本输入:用1,3,5,9,16,22切割的木材，当我们第一次以中间值9开始时，会有最小的cost=163，然后我们会得到1,3,5，9，9,16,22标记的木材，现在我们先解决左边的木材，我们会得到1，3，5，5，现在我们又切了1,35,9，和剩下的9,16,22，现在在操作这个木材的时候，我们已经把所有的标记都剪掉了，这个列表将是1,35,916,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次；显著减少。我们可以看到这些缓存被很好地利用了。

在组合问题中经常出现的加泰罗尼亚数给出了所有可能的切割序列的个数。

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

如果你有两个以上的分数，在任何特定的地方裁剪的成本是在那里切割的成本，加上削减其余的成本。因此，削减成本就是最低成本或这些成本。这应该足以填补一些聪明的东西。

这个解决方案会随着许多削减而缓慢运行。为了解决这个问题，你应该查一查“回忆录”。