ตรวจสอบว่าเป็นไปได้ที่จะได้รับผลรวมจากชุดขององค์ประกอบที่กำหนดใน Python

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

ดังนั้น หากอินพุตเป็น nums =[2, 3, 5] sum =28 ผลลัพธ์จะเป็น True ตามที่เราได้ 26 โดยใช้ 5 + 5 + 5 + 5 + 3 + 3 + 2

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

• สูงสุด :=1,000
• ตาราง :=อาร์เรย์ของขนาดโฆษณา MAX เติมด้วย 0
• กำหนดฟังก์ชัน util() นี้จะใช้เวลา nums
• ตาราง[0] :=1
• เรียงเลขรายการ
• สำหรับฉันในช่วง 0 ถึงขนาดของ nums - 1 ทำ
  • val :=nums[i]
  • ถ้า table[val] ไม่ใช่ศูนย์ ดังนั้น
    • ติดตามตอนต่อไป
  • สำหรับ j ในช่วง 0 ถึง MAX - val - 1 ทำ
    • ถ้า table[j] ไม่ใช่ศูนย์ ดังนั้น
      • ตาราง[j + val] :=1
• จากวิธีหลัก ให้ทำดังนี้ -
• util(nums)
• ถ้า table[sum] ไม่ใช่ศูนย์ ดังนั้น
  • คืนค่า True
• คืนค่าเท็จ

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

ตัวอย่าง

MAX = 1000
table = [0] * MAX
def util(nums):
   table[0] = 1
   nums.sort()
   for i in range(len(nums)):
      val = nums[i]
      if table[val]:
         continue
      for j in range(MAX - val):
         if table[j]:
            table[j + val] = 1
def solve(nums, sum):
   util(nums)
   if table[sum]:
      return True
   return False
nums = [2, 3, 5]
sum = 28
print (solve(nums, sum))

อินพุต

[2, 3, 5], 28

ผลลัพธ์

True