โปรแกรมหาค่าต่ำสุดจากผลรวมของค่าโหนดของแผนผังย่อยใน Python

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

ดังนั้น หากอินพุตเป็น n =6, edge_list =[[1, 2], [1, 3], [2, 4], [3, 5], [3, 6]], ค่า =[15, 25, 15, 55, 15, 65] แล้วเอาท์พุตจะเป็น 0

หากนำขอบ (1,2) ออก ผลรวมของน้ำหนักจะกลายเป็น 80, 110 ส่วนต่างคือ 30

หากนำขอบ (1,3) ออก ผลรวมของน้ำหนักจะกลายเป็น 95, 95 ส่วนต่างคือ 0

หากนำขอบ (2,4) ออก ผลรวมของน้ำหนักจะกลายเป็น 55, 135 ส่วนต่างคือ 80

หากนำขอบ (3,5) ออก ผลรวมของน้ำหนักจะกลายเป็น 15, 175 ส่วนต่างคือ 160

หากนำขอบ (3,6) ออก ผลรวมของน้ำหนักจะกลายเป็น 65, 125 ส่วนต่างคือ 60

ดังนั้นน้ำหนักขั้นต่ำคือ 0

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

adj_list :=รายการใหม่ของขนาด n ที่มีรายการว่าง
สำหรับแต่ละขอบใน edge_list ให้ทำ
- u :=edge[0]
- v :=edge[1]
- แทรก v-1 ที่ส่วนท้ายของ adj_list[u-1]
- แทรก u-1 ที่ส่วนท้ายของ adj_list[v-1]
value_list :=รายการใหม่ของขนาด n เริ่มต้นด้วย 0s
not_visited :=แผนที่ใหม่ขนาด i โดยที่ i คือจำนวนรายการที่ไม่ว่างเปล่าใน adj_list
ในขณะที่ not_visited นั้นไม่ว่างเปล่า ให้ทำ
- สำหรับทุกๆ ฉันใน not_visited ทำ
  - value_list[i] :=value_list[i] + ค่า[i]
  - ถ้าความยาวของ (adj_list[i]) ไม่ใช่ศูนย์ ดังนั้น
    - ลบ i จาก adj_list[adj_list[i, 0]]
    - value_list[adj_list[i, 0]] :=value_list[adj_list[i, 0]] + value_list[i]
- สำหรับทุกๆ ฉันใน not_visited ทำ
  - ถ้า len(adj_list[i]) และ len(adj_list[adj_list[i, 0]]) ==1 แล้ว
    - not_visited :=รายการใหม่ที่มี adj_list[i, 0]
return_val :=|sum(values) - 2 * value_list[0]|
สำหรับฉันในช่วง 1 ถึง n ทำ
- decision_val :=|sum(values) - 2 * value_list[i]|
- ถ้าคำตัดสิน_val
- return_val :=การตัดสินใจ_val

คืนสินค้า_val

ตัวอย่าง

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

def solve(n, edge_list, values):
   adj_list = [[] for i in range(n)]

   for edge in edge_list:
      u = edge[0]
      v = edge[1]
      adj_list[u-1].append(v-1)
      adj_list[v-1].append(u-1)

   value_list = [0] * n
   not_visited = {i for i in range(n) if len(adj_list[i]) == 1}
   while(len(not_visited)):
      for i in not_visited:
         value_list[i] += values[i]
         if(len(adj_list[i])):
            adj_list[adj_list[i][0]].remove(i)
            value_list[adj_list[i][0]] += value_list[i]
      not_visited = {adj_list[i][0] for i in not_visited if
         len(adj_list[i]) and len(adj_list[adj_list[i][0]]) == 1}
   return_val = abs(sum(values) - 2 * value_list[0])

   for i in range(1, n):
      decision_val = abs(sum(values) - 2 * value_list[i])
      if decision_val < return_val:
         return_val = decision_val
   return return_val

print(solve(6, [[1, 2], [1, 3], [2, 4], [3, 5], [3, 6]], [10, 20, 10, 50, 10, 60]))

อินพุต

6, [[1, 2], [1, 3], [2, 4], [3, 5], [3, 6]], [10, 20, 10, 50, 10, 60]

โปรแกรมหาค่าต่ำสุดจากผลรวมของค่าโหนดของแผนผังย่อยใน Python

ตัวอย่าง

อินพุต

ผลลัพธ์