Chương trình Python tìm lợi nhuận tối đa cắt thanh sắt bán cùng độ dài

Cho danh sách độ dài thanh rodLen, lợi nhuận trên đơn vị độ dài profit, chi phí mỗi lần cắt cost. Chỉ bán được các thanh cùng độ dài. Cắt thanh thành các đoạn nguyên, mỗi cắt tốn cost. Tìm lợi nhuận tối đa.

Ví dụ

Input: rodLen = [7, 10], profit = 6, cost = 4

Output: 82

Giải thích: Cắt 7 → 5+2 (1 cắt), cắt 10 → 5+5 (1 cắt). Bán 3 thanh độ dài 5: (5+5+5)*6 - 2*4 = 90 - 8 = 82.

Thuật toán (Thử mọi độ dài cắt có thể)

1. Duyệt độ dài thanh mục tiêu cuts từ 1 đến max(rodLen).
2. Với mỗi cuts, tính lợi nhuận từ mỗi thanh gốc:
   • Số đoạn được: c_count = rod_len // cuts
   • Tổng độ dài bán được: total_len = c_count * cuts
   • Nếu thanh chia hết (rod_len == total_len) → số cắt = c_count - 1 (không cắt đoạn cuối).
   • Lợi nhuận thanh này: total_len * profit - cost * c_count
   • Nếu lợi nhuận < 0 → bỏ qua thanh này.
3. Tổng lợi nhuận cho cuts này, cập nhật max.

Mã nguồn Python

def solve(rodLen, profit, cost):
    if not rodLen:
        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

# Test
rodLen = [7, 10]
profit = 6
cost = 4
print(solve(rodLen, profit, cost))  # Output: 82

Độ phức tạp

• Thời gian: O(n * L), L = max(rodLen).
• Không gian: O(1).