python - 削减成本算法优化

Question

我有一张木板，并在木板上打了 N 个标记。现在我必须在木板上切割所有标记，以使切割所有标记的成本最小。现在假设我先切割第 i 个标记，然后成本是通过使用两个作为输入的乘数 a 和 b 给出的，成本是 a*(left)+b*(right)，其中 left 和 right 是切割后木材剩余部分的大小。例如，如果我有一个长度为 10 且 a=3 和 b=4 的木头，如果我有 ex 的标记列表:[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] 现在在操作这 block 木头时我们已经切割了所有标记并且列表将是 [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 给出这经常出现在组合问题中。