Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm kiếm lợi nhuận tối đa sau khi cắt các thanh và bán các thanh có cùng chiều dài bằng Python

Giả sử chúng ta có một danh sách độ dài thanh được gọi là rodLen. Chúng tôi cũng có hai số nguyên khác được gọi là lợi nhuận và chi phí, đại diện cho lợi nhuận trên mỗi chiều dài và chi phí mỗi lần cắt. Chúng tôi có thể kiếm được lợi nhuận trên một đơn vị chiều dài của thanh nhưng chúng tôi chỉ có thể bán các thanh có cùng chiều dài. Chúng ta cũng có thể cắt một thanh thành hai đoạn sao cho độ dài của chúng là số nguyên, nhưng chúng ta phải trả chi phí cho mỗi lần cắt. Chúng ta có thể cắt một thanh bao nhiêu lần tùy thích. Chúng tôi phải tìm ra lợi nhuận tối đa mà chúng tôi có thể tạo ra.

Vì vậy, nếu đầu vào giống như rodLen =[7, 10] lợi nhuận =6 chi phí =4, thì đầu ra sẽ là 82, vì chúng ta có thể cắt thanh có chiều dài 7 thành hai thanh, có chiều dài 5 và 2. Khi đó chúng ta có thể cắt que có chiều dài 10 thành hai que đều có chiều dài là 5. Sau đó bán cả 3 que có chiều dài là 5 với tổng lãi là (5 + 5 + 5) * 6 - (2 * 4) =82.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • n:=kích thước của rodLen
  • nếu n giống 0, thì
    • trả về 0
  • l_max:=tối đa của rodLen
  • p_max:=0
  • để cắt trong phạm vi từ 1 đến l_max, hãy thực hiện
    • p_cut:=0
    • đối với mỗi rod_len trong rodLen, thực hiện
      • nếu rod_len
      • chuyển sang lần lặp tiếp theo
    • c_count:=rod_len / cut
    • total_len:=c_count * lần cắt
    • nếu rod_len giống với total_len, thì
      • c_count:=c_count - 1
    • curr_profit:=total_len * lợi nhuận - chi phí * c_count
    • nếu curr_profit <0, thì
      • chuyển sang lần lặp tiếp theo
    • p_cut:=p_cut + curr_profit
  • p_max:=tối đa là p_max và p_cut
  • trả về p_max

    • Ví dụ

    Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

    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))

    Đầu vào 

    [7, 10], 6, 4

    Đầu ra 

    82