Chương trình Python bài toán cắt thanh (Cutting a Rod)

Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:

Đề bài – Cho thanh dài n và mảng giá chứa giá các đoạn nhỏ hơn n. Cần tìm giá trị lớn nhất bằng cách cắt thanh và bán các đoạn.

Sử dụng quy hoạch động.

Hãy quan sát giải pháp trong triển khai dưới đây:

Ví dụ

# DP cắt thanh
INT_MIN = -32767

def cutRod(price, n):
    val = [0 for x in range(n + 1)]
    val[0] = 0
    # bottom-up
    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("Giá trị lớn nhất:", cutRod(arr, size))

Kết quả

Giá trị lớn nhất: 21

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python bài toán cắt thanh.