Chương trình Python để cắt một thanh

Trong bài viết này, chúng ta sẽ tìm hiểu về giải pháp cho câu hỏi được đưa ra bên dưới.

Tuyên bố sự cố - Ta được cho một thanh có chiều dài n và một dãy giá chứa các giá của tất cả các mảnh có kích thước nhỏ hơn n. Chúng tôi cần xác định giá trị tối đa có thể đạt được bằng cách cắt thanh và bán các phần của nó.

Chúng tôi sẽ sử dụng phương pháp lập trình động để giải quyết vấn đề.

Bây giờ chúng ta hãy quan sát giải pháp trong việc triển khai bên dưới−

Ví dụ

# A Dynamic Programming solution for Rod cutting problem
INT_MIN = -32767
# cut function
def cutRod(price, n):
   val = [0 for x in range(n + 1)]
   val[0] = 0
   # bottom up manner
   for i in range(1, n + 1):
      max_val = INT_MIN
      for j in range(i):
         max_val = max(max_val, price[j] + val[i-j-1])
      val[i] = max_val
   return val[n]
# main
arr = [2, 4, 7, 9, 11, 16, 16, 21]
size = len(arr)
print("Maximum Obtainable Value is " + str(cutRod(arr, size)))

Đầu ra

Maximum Obtainable Value is 21

Tất cả các biến được khai báo trong phạm vi cục bộ và các tham chiếu của chúng được hiển thị trong hình trên.

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu về cách chúng ta có thể tạo một Chương trình Python để Cắt một thanh.