我有一个MxN尺寸的矩形板，需要将其切成1x1大小的方头。这些正方形中的每个都有一定的价值，切割成本是切割中涉及的所有正方形的值之和。我想找到最低可能的费用。
例
假设我们有2x3的木板，并且正方形peices的值以矩阵形式给出：
2 7 5
1 9 5
现在，如果我们首先进行水平切割，则成本将为（2 + 7 + 5 + 1 + 9 + 5 = 29），我们将获得两个较小的方形矩形板：
2 7 5和1 9 5接下来，我们削减1,9和5（成本= 1 + 9 + 5 = 15），然后削减2,7和5（成本= 2 + 7 + 5 = 14）。因此，我们有以下委员会：
2 7，5，1 9，5此后，我们削减1和9（成本= 1 + 9 = 10），然后削减2和7（成本= 2 + 7 = 9）。我们还有以下平方：
2，7，5，1，9，5现在我们将停止，因为所有剩余的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，但我希望它足以满足您的需求。