ตรวจสอบว่าผลรวมอาเรย์สามารถสร้าง K โดยสามการดำเนินการใน Python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า num และค่าบวก K เราสามารถดำเนินการใด ๆ ในสามค่านี้กับ nums -

• ลบเลขหนึ่งตัว
• เพิ่มดัชนี (เริ่มจากดัชนี 1) ของตัวเลขไปยังตัวเลขเอง
• ลบดัชนีของตัวเลขออกจากตัวตัวเลข

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

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[1,2,3,7] k =8 ผลลัพธ์จะเป็น True เนื่องจากเราสามารถลบดัชนี 2 และ 3 ออกจาก 2 และ 3 เพื่อสร้างอาร์เรย์เช่น [1, 0, 0, 7] ดังนั้นตอนนี้ผลรวมคือ 8 =k

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

• ขนาด :=100
• กำหนดฟังก์ชัน is_ok() นี่จะใช้เวลา i, ผลรวม, k, nums, ตาราง
• n :=ขนาดของ nums
• ถ้ารวม <=0 แล้ว
  • คืนค่าเท็จ
• ถ้าฉัน>=n แล้ว
  • ถ้าผลรวมเท่ากับ k แล้ว
    • คืนค่า True
• คืนค่าเท็จ
• ถ้า table[i, total] ไม่ใช่ -1 แล้ว
  • กลับตาราง[i, ทั้งหมด]
• table[i, total] :=1 เมื่อ (is_ok(i+1, total - 2 * nums[i], k, nums, table) ไม่เป็นศูนย์ หรือ is_ok(i+1, Total, k, nums ตาราง) ไม่ใช่ศูนย์) มิฉะนั้น 0
• table[i, total] :=1 เมื่อ (is_ok(i+1, Total -(i+1) , k, nums, table) หรือ table[i, total]) มิฉะนั้น 0
• table[i, total] :=1 เมื่อ (is_ok(i+1, total + i + 1, k, nums, table) หรือ table[i, total]) หรือ 0
• กลับตาราง[i, ทั้งหมด]
• จากวิธีหลัก ให้ทำดังนี้ -
• ผลรวม :=ผลรวมขององค์ประกอบทั้งหมดเป็น nums
• table :=อาร์เรย์ความยาวเท่ากับขนาดและเติม -1
• สำหรับฉันในช่วง 0 ถึงขนาด ทำ
  • table[i] :=อาร์เรย์ที่มีความยาวเท่ากับขนาดและเติมด้วย -1
• ผลตอบแทน is_ok(0, ทั้งหมด, k, nums, ตาราง)

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

ตัวอย่าง

size = 100
def is_ok(i, total, k, nums, table):
   n = len(nums)
   if total <= 0:
      return False
   if i >= n:
      if total == k:
         return True
      return False
   if table[i][total] != -1:
      return table[i][total]
   table[i][total] = is_ok(i+1, total - 2 * nums[i], k, nums, table) or is_ok(i+1, total, k, nums, table)
   table[i][total] = is_ok(i+1, total - (i+1), k, nums, table) or table[i][total] table[i][total] = is_ok(i+1, total + i + 1, k, nums, table) or table[i][total]
   return table[i][total]
def solve(nums, k):
   total = sum(nums)
   table = [-1]*size
   for i in range(size):
      table[i] = [-1]*size
   return is_ok(0, total, k, nums, table)
nums = [1,2,3,7]
k = 8
print(solve(nums, k))

อินพุต

[1,2,3,7], 8

ผลลัพธ์

True