用 Python 编写程序，在切割杆并出售相同长度的杆后找到最大利润

pythonserver side programmingprogramming更新于 2026/1/18 14:36:17

假设我们有一个名为 rodLen 的杆长度列表。我们还有另外两个整数，分别称为利润和成本，分别表示每单位长度的利润和每次切割的成本。我们可以从每单位长度的杆中获得利润，但我们只能出售长度相同的杆。我们也可以将杆切成两段，使它们的长度为整数，但每次切割我们都必须支付成本金额。我们可以根据需要多次切割杆。我们必须找到可以赚取的最大利润。

因此，如果输入为 rodLen = [7, 10] 利润 = 6 成本 = 4，则输出将为 82，因为我们可以将长度为 7 的杆切成两根杆，长度分别为 5 和 2。然后，我们可以将长度为 10 的杆切成两根杆，长度均为 5。然后出售所有 3 根长度为 5 的杆，总利润为 (5 + 5 + 5) * 6 - (2*4) = 82。

为了解决这个问题，我们将遵循以下步骤 −

n := rodLen 的大小
如果 n 与 0 相同，则
- 返回 0
l_max := rodLen 的最大值
p_max := 0
对于范围从 1 到 l_max 的切割，执行
- p_cut := 0
- 对于 rodLen 中的每个 rod_len，执行
  - 如果 rod_len < 切割，则
    - 进行下一次迭代
  - c_count := rod_len / cuts
  - total_len := c_count * cuts
  - 如果 rod_len 与 total_len 相同，则
    - c_count := c_count - 1
  - curr_profit := total_len * profits - cost * c_count
  - 如果 curr_profit < 0，然后
    - 进行下一次迭代
  - p_cut := p_cut + curr_profit
- p_max := p_max 和 p_cut 的最大值
返回 p_max

示例

让我们看看下面的实现以便更好地理解 −

def solve(rodLen, profit, cost):
   n = len(rodLen)
   if n == 0:
      return 0
   l_max = max(rodLen)
   p_max = 0

   for cuts in range(1, l_max + 1):
      p_cut = 0
      for rod_len in rodLen:
         if rod_len < cuts:
            continue
         c_count = rod_len // cuts
         total_len = c_count * cuts
         if rod_len == total_len:
            c_count -= 1
         curr_profit = total_len * profit - cost * c_count
         if curr_profit < 0:
            continue
         p_cut += curr_profit
      p_max = max(p_max, p_cut)
   return p_max

rodLen = [7, 10]
profit = 6
cost = 4
print(solve(rodLen, profit, cost))