ค้นหาต้นทุนการปรับขั้นต่ำของอาร์เรย์ใน Python

สมมติว่าเรามีอาร์เรย์ของจำนวนบวก เราแทนที่แต่ละองค์ประกอบจากอาร์เรย์อาร์เรย์นั้นเพื่อให้ความแตกต่างระหว่างสององค์ประกอบที่อยู่ติดกันในอาร์เรย์นั้นน้อยกว่าหรือเท่ากับเป้าหมายที่กำหนด ตอนนี้ เราต้องลดต้นทุนการปรับปรุง ดังนั้นผลรวมของความแตกต่างระหว่างมูลค่าใหม่กับมูลค่าเก่า แม่นยำยิ่งขึ้น เราย่อ ∑|A[i] – Anew[i]| โดยที่ i อยู่ในช่วง 0 ถึง n-1 ในที่นี้ n จะแสดงเป็นขนาดของ A และ Anew คืออาร์เรย์ที่มีความแตกต่างที่อยู่ติดกันน้อยกว่าหรือเท่ากับเป้าหมาย

ดังนั้น หากอินพุตเป็น [56, 78, 53, 62, 40, 7, 26, 61, 50, 48] เป้าหมาย =20 ผลลัพธ์จะเป็น 25

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

• n :=ขนาดของ arr

• ตาราง :=[[0 สำหรับฉันในช่วง 0 ถึง M + 1] สำหรับฉันในช่วง 0 ถึง n]

• สำหรับ j ในช่วง 0 ถึง M + 1 ทำ

  • table[0, j] :=|j - arr[0]|

• สำหรับผมอยู่ในช่วง 1 ถึง n ทำ

  • สำหรับ j ในช่วง 0 ถึง M + 1 ทำ

    • ตาราง[i, j] :=100000000

    • สำหรับ k ในช่วงสูงสุดของ (j-target และ 0) และต่ำสุดของ (M และ j + เป้าหมาย) ทำ

      • table[i,j] =ค่าต่ำสุดของ table[i,j], table[i - 1,k] + |arr[i] - j|

• ตอบ :=10000000

• สำหรับ j ในช่วง 0 ถึง M + 1 ทำ

  • ans =ขั้นต่ำของ ans และ table[n-1, j]

  • กลับมาอีกครั้ง

ตัวอย่าง

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

M = 100
def get_min_cost(arr, target):
   n = len(arr)
   table = [[0 for i in range(M + 1)] for i in range(n)]
   for j in range(M + 1):
      table[0][j] = abs(j - arr[0])
   for i in range(1, n):
      for j in range(M + 1):
         table[i][j] = 100000000
         for k in range(max(j - target, 0), min(M, j + target) + 1):
            table[i][j] = min(table[i][j], table[i - 1][k] + abs(arr[i] - j))
   ans = 10000000
   for j in range(M + 1):
      ans = min(ans, table[n - 1][j])
   return ans
arr= [56, 78, 53, 62, 40, 7, 26, 61, 50, 48]
target = 20
print(get_min_cost(arr, target))

อินพุต

[56, 78, 53, 62, 40, 7, 26, 61, 50, 48], 20

ผลลัพธ์

35