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

สมมติว่าเรามีรายการความยาวก้านที่เรียกว่า rodLen เรายังมีจำนวนเต็มอีกสองจำนวนที่เรียกว่ากำไรและต้นทุน ซึ่งหมายถึงกำไรต่อความยาวและต้นทุนต่อการตัด เราสามารถทำกำไรได้ต่อหน่วยความยาวของแท่ง แต่เราสามารถขายแท่งที่มีความยาวเท่ากันทั้งหมดเท่านั้น นอกจากนี้เรายังสามารถตัดไม้เรียวเป็นสองชิ้นเพื่อให้ความยาวเป็นจำนวนเต็ม แต่เราต้องจ่ายค่าใช้จ่ายสำหรับการตัดแต่ละครั้ง เราสามารถตัดไม้เรียวได้หลายครั้งตามต้องการ เราต้องหากำไรสูงสุดที่เราสามารถทำได้

ดังนั้นหากอินพุตเป็นเหมือน rodLen =[7, 10] กำไร =6 ต้นทุน =4 ผลลัพธ์จะเป็น 82 เนื่องจากเราสามารถตัดท่อนยาว 7 ออกเป็นสองท่อนโดยมีความยาว 5 และ 2 เราก็ทำได้ ตัดไม้เรียวยาว 10 ออกเป็นสองท่อน ยาวทั้ง 5 ท่อน แล้วขายทั้ง 3 ท่อน ยาว 5 ให้ได้กำไรรวม (5 + 5 + 5) * 6 - (2*4) =82

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ rodLen
• ถ้า n เหมือนกับ 0 แล้ว
  • คืน 0
• l_max :=สูงสุดของ rodLen
• p_max :=0
• สำหรับการตัดในช่วง 1 ถึง l_max ทำ
  • p_cut :=0
  • สำหรับแต่ละ rod_len ใน rodLen ทำ
    • ถ้า rod_len <ตัด แล้ว
      • ติดตามตอนต่อไป
    • c_count :=rod_len / ตัด
    • total_len :=c_count * ตัด
    • ถ้า rod_len เหมือนกับ total_len แล้ว
      • c_count :=c_count - 1
    • curr_profit :=total_len * กำไร - ต้นทุน * c_count
    • ถ้า curr_profit <0 แล้ว
      • ติดตามตอนต่อไป
    • p_cut :=p_cut + curr_profit
  • p_max :=สูงสุดของ p_max และ p_cut
• คืน p_max

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

อินพุต

[7, 10], 6, 4

ผลลัพธ์

82