Kiểm tra xem có thể nhận tổng đã cho từ một tập hợp các phần tử nhất định trong Python hay không

Giả sử chúng ta có một mảng gọi là nums và một tổng giá trị khác. Chúng tôi phải kiểm tra xem có thể lấy tổng bằng cách thêm các phần tử có trong nums hay không, chúng tôi có thể chọn một phần tử nhiều lần.

Vì vậy, nếu đầu vào là nums =[2, 3, 5] sum =28, thì đầu ra sẽ là True vì chúng ta có thể lấy 26 bằng cách sử dụng 5 + 5 + 5 + 5 + 3 + 3 + 2

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• MAX:=1000
• table:=một mảng quảng cáo có kích thước MAX lấp đầy bằng 0
• Xác định một hàm dùng (). Quá trình này sẽ mất vài giây
• bảng [0]:=1
• sắp xếp các số trong danh sách
• đối với tôi trong phạm vi từ 0 đến kích thước là nums - 1, thực hiện
  • val:=nums [i]
  • nếu bảng [val] khác 0, thì
    • chuyển sang lần lặp tiếp theo
  • cho j trong phạm vi 0 đến MAX - val - 1, thực hiện
    • nếu bảng [j] khác 0, thì
      • bảng [j + val]:=1
• Từ phương thức chính, hãy làm như sau -
• sử dụng (nums)
• nếu bảng [sum] khác 0, thì
  • trả về True
• trả về Sai

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

[2, 3, 5], 28

Đầu ra

True