削减成本算法优化 [英] cutting cost algorithm optimization
问题描述
我有一块木板，并且在木板上给了N标记.现在我必须切割木板上的所有标记，以使切割所有标记的成本降至最低.现在假设我先切割第i个标记，然后切割通过使用两个乘数a和b作为输入来给出成本，成本是a *(左)+ b *(右)，其中左和右是切割后木材剩余部分的大小.例如，如果我有一个长度为10，a = 3和b = 4的木材，如果我有ex的标记列表:[1,3,5,7,10]所以我不能切割第一个和最后一个标记，因为它们是该标记的起点和终点木材，因此，假设我首先从标记7开始，则切割成本将为3 *(7-1)+ 4 *(10-7)= 18 + 12 = 30，现在我要使用的木材是从标记开始的木材1表示标记7，其他表示标记7标记到木广告的末尾，我将重复此过程，直到所有标记都被切掉为止.
I have a wood sheet and have given N mark on wood sheet.Now i have to cut all the marks on wood sheet such that cost of cutting all the marks in minimum.Now suppose i first cut the i th mark then the cost is given by using two multipliers a and b which are inputs and the cost is a*(left)+b*(right) where left and right are the size of remaining part of the wood after cutting .for example if i have a wood of length 10 and a=3 and b=4 and if i have mark list for ex: [1,3,5,7,10] so i cant cut first and last mark because they are the starting and end point of the wood so suppose if i start with mark 7 first then cost of cutting will be 3*(7-1)+4*(10-7)=18+12=30 and now the wood which i would have is one starting with mark 1 to mark 7 and other would be one with mark 7 to the end of the wood ad i would repeat the process till all of the marks have been cut .
现在，在阅读了问题之后，我立即想到，为了以最小的成本切割木材，我首先需要找到中点(切割点的中位数)，然后在这里我应该切割木材并再次重复此过程直到木材没有切割点，但我在解决切割后获得的正确木材方面遇到了问题
Now after reading the question it immediately came to my mind that in order to cut the wood in minimum cost i first need to find the mid point(median of cut points) and there i should cut the wood and repeat this process again and again till the wood has no cut points left but i am having problem in solving the right wood obtained after cutting
样本输入:以[1,3,5,9,16,22]砍伐的木材在我们首先从中位数9开始时的最低成本= 163，然后我们将标记为[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]并且此操作的成本将最低
sample input:wood having cut with [1,3,5,9,16,22] would have minimum cost=163 when we first start with median 9 then we would have wood of mark[1,3,5,9] and [9,16,22] now first solving the left wood we would have [1,3,5][5,9],now again cutting we have [1,3][3,5][5,9] and the one which was left [9,16,22] now on operating this wood we have cut all the marks and the list would be [1,3][3,5][5,9][9,16][16,22] and the cost on this operation would be minimum
这是我的代码:
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，该函数将剪切序列应用于标记序列，因此您可以看到剪切按此顺序进行.
Firstly, here's a recursive generator solve_gen that checks all the possible cutting sequences and then chooses the minimum one. Although the code is compact, and it runs ok if the number of marks is small, it soon gets rather inefficient as the number of marks increases. I've also included a function apply_cuts that applies a sequence of cuts to a mark sequence, so you can see the cuts happening in that order.
solve_gen使用全局count跟踪进行的递归调用的数量. count对于该算法的操作不是必需的，但它可以指示功能正在执行的工作量.
solve_gen uses a global count to keep track of the number of recursive calls that get made. count isn't necessary for the operation of the algorithm, but it gives us an indication of how much work the function is doing.
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具有更长的标记序列.
FWIW, here are the results for the same a & b with a longer mark sequence.
(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
我们可以通过在递归的每个阶段找到最小值，而不是找到所有可能性中的最小值，来提高效率.但是，当算法研究各种切削选项时，它通常会重复之前所做的计算.因此，我们可以使用缓存来提高代码的效率，也就是说，我们将先前的结果存储在字典中，因此，如果我们需要再次进行相同的切割，我们可以在缓存中查找它，而不用重新计算它.
We can make this more efficient by finding the minima at each stage of the recursion, rather than finding the minimum of all the possibilities. However, as the algorithm investigates the various cutting options it often repeats calculations that it's done before. So we can make the code much more efficient by using caching, i.e, we store previous results in a dictionary, so if we ever need to make the same cut again we can just look it up in the cache instead of recalculating it.
我们可以编写自己的缓存，但是functools模块提供了 lru_cache 可用作装饰器.我们也可以为cost函数提供一个缓存，尽管它的计算非常简单，因此缓存可能不会在那里节省很多时间. lru_cache的一个不错的功能是它还可以提供缓存统计信息，这让我们知道了缓存的有用性.
We could code our own cache, but the functools module provides lru_cache which can be used as a decorator. We can also give the cost function a cache, although its calculations are fairly simple, so caching probably doesn't save much time there. A nice feature of lru_cache is that it can also provide cache statistics, which lets us know how useful the cache is.
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)
幸运的是，我们得到的结果与以前相同. ;)请注意，现在递归计数要低得多.让我们尝试使用更长的标记序列.
Fortunately, we get the same results as before. ;) Notice that the recursion count is now much lower. Let's try it with that longer mark sequence.
(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；大幅减少.我们可以看到缓存得到了很好的利用.
The recursion count is a mere 55 compared to the previous 41990; a significant reduction. And we can see that the caches are being well-used.
FWIW，所有可能的切割顺序的编号由加泰罗尼亚编号给出通常会遇到组合问题.
FWIW, the number of all the possible cutting sequences is given by the Catalan numbers which often crop up in combinatorial problems.
这篇关于削减成本算法优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
