在Python中找到最大利润的程序,通过切割杆并出售相同长度的杆
假设我们有一个叫做rodLen的杆长度列表。我们还有另外两个整数称为利润和成本,它们表示每个长度的利润和每次切割的成本。我们可以获得每个杆的单位长度的利润,但我们只能出售长度相同的杆。我们还可以将杆割成两块,使它们的长度为整数,但我们必须为每次切割支付成本费用。我们可以随意切割杆。我们必须找到我们可以获得的最大利润。
因此,如果输入如rodLen = [7, 10] profit = 6 cost = 4,则输出将为82,因为我们可以将长度为7的杆切成两根,长度为5和2。然后我们把长度为10的杆切成两根,长度都为5。然后将长度为5的所有3根杆出售,总利润为(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 < cuts,那么
- 继续下一个迭代
- c_count:= rod_len / cuts
- total_len:= c_count * cuts
- 如果rod_len与total_len相同,则
- c_count:=c_count – 1
- curr_profit:= total_len * profit – 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))
输入
[7, 10],6,4
输出
82