โปรแกรมหากำไรสูงสุดตัดไม้ขายความยาวเท่ากันใน Python

คำอธิบายปัญหา

กำหนดลิสต์ความยาวไม้ rodLen, profit (กำไรต่อหน่วยยาว), cost (ค่าตัดต่อครั้ง) ตัดไม้เป็นชิ้นความยาวเท่ากัน (จำนวนเต็ม) ขายเฉพาะชิ้นที่ความยาวเท่ากันทุกชิ้น หากำไรสูงสุด

ตัวอย่าง

rodLen = [7, 10], profit = 6, cost = 4 → Output: 82

• ตัด 7 → 5+2 (1 ครั้ง), ตัด 10 → 5+5 (1 ครั้ง)
• ได้ไม้ยาว 5 ทั้งหมด 3 ชิ้น: (5+5+5)*6 - 2*4 = 90 - 8 = 82

ขั้นตอนการแก้ปัญหา

1. ลองความยาวขาย cuts = 1 ถึง max(rodLen)
2. แต่ละไม้: c_count = rod_len // cuts ชิ้น, total_len = c_count * cuts
3. ถ้าไม้หารลงตัว (rod_len == total_len) ตัดได้ c_count - 1 ครั้ง (ชิ้นสุดท้ายไม่ต้องตัด)
4. curr_profit = total_len * profit - cost * c_count ถ้า < 0 ข้าม
5. รวมกำไรทุกไม้ หาค่า max

การตนการทำงาน (Python)

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))  # Output: 82

อินพุต / เอาต์พุต

Input:  [7, 10], 6, 4
Output: 82