我有一个MxN尺寸的矩形板,需要将其切成1x1大小的方头。这些正方形中的每个都有一定的价值,切割成本是切割中涉及的所有正方形的值之和。我想找到最低可能的费用。



假设我们有2x3的木板,并且正方形peices的值以矩阵形式给出:

2 7 5
1 9 5


现在,如果我们首先进行水平切割,则成本将为(2 + 7 + 5 + 1 + 9 + 5 = 29),我们将获得两个较小的方形矩形板:

2 7 51 9 5

接下来,我们削减1,9和5(成本= 1 + 9 + 5 = 15),然后削减2,7和5(成本= 2 + 7 + 5 = 14)。因此,我们有以下委员会:

2 751 95

此后,我们削减1和9(成本= 1 + 9 = 10),然后削减2和7(成本= 2 + 7 = 9)。我们还有以下平方:

275195

现在我们将停止,因为所有剩余的pepes仅为1x1。

因此,总成本为77。这只是给出最低成本的方法之一。还有其他切割板的方法可能会产生相同或更高的成本。

那么,如何找到最低成本?感谢帮助!

最佳答案

这花了我一段时间,而且效率不高,但是对于小难题,应该没问题。

class Piece:
    def __init__(self, data, w, h):
        self.data = data
        self.w = w
        self.h = h

    def cut_vertically(self, x):
        a = Piece([v for i, v in enumerate(self.data) if i % self.w <= x], x + 1, self.h)
        b = Piece([v for i, v in enumerate(self.data) if i % self.w > x], self.w - x - 1, self.h)
        s = sum(self.data)
        return a, b, s

    def cut_horizontally(self, y):
        a = Piece([v for i, v in enumerate(self.data) if i < self.w * (y + 1)], self.w, y + 1)
        b = Piece([v for i, v in enumerate(self.data) if i >= self.w * (y + 1)], self.w, self.h - y - 1)
        s = sum(self.data)
        return a, b, s

    def generate_cuts(self):
        for x in range(self.w - 1):
            yield self.cut_vertically(x)
        for y in range(self.h - 1):
            yield self.cut_horizontally(y)

def scores(p):
    if p.w == 1 and p.h == 1:
        yield 0

    for a, b, s in p.generate_cuts():
        for s1 in scores(a):
            for s2 in scores(b):
                yield s + s1 + s2

p = Piece([2, 7, 5, 1, 9, 5], 3, 2)

min_score = None
for score in scores(p):
    if not min_score or score < min_score:
        min_score = score

print(score)


它没有任何错误检查,因此您必须确保正确设置Piece,但我希望它足以满足您的需求。

07-28 07:40