Tìm số lượng tối đa các tổng hợp của một số trong Python

Giả sử chúng ta có một số N cho trước trong phạm vi (1 <=N <=10 ^ 9), chúng ta phải biểu diễn N dưới dạng tổng của số lớn nhất có thể của các tổng hợp và trả về số lớn nhất này, nếu không khi chúng ta không thể tìm thấy bất kỳ phần tách nào, hãy trả về -1.

Vì vậy, nếu đầu vào là 16, thì đầu ra sẽ là 4 vì 16 có thể được viết là 4 + 4 + 4 + 4 hoặc 8 + 8, nhưng (4 + 4 + 4 + 4) có tổng tối đa.

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

max_val:=16
Định nghĩa một hàm pre_calc (). Điều này sẽ mất
table:=danh sách kích thước max_val, sau đó lưu trữ -1 ở mỗi vị trí
bảng [0]:=0
v:=[4, 6, 9]
đối với tôi trong phạm vi 1 đến max_val, tăng 1, thực hiện
- đối với k trong phạm vi 0 đến 2, thực hiện
  - j:=v [k]
  - nếu i> =j và bảng [i - j] không phải là -1, thì
    - table [i]:=tối đa của table [i], table [i - j] + 1
bảng trả lại
Xác định một hàm max_summ (). Điều này sẽ có bàn, n
nếu n
- bảng trả về [n]
nếu không,
- t:=số nguyên của ((n - max_val) / 4) + 1
- trả về bảng t + [n - 4 * t]
Từ phương thức chính, thực hiện như sau -
bảng:=pre_calc ()
display max_summ (table, n)

Ví dụ

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

global max_val
max_val = 16
def pre_calc():
   table = [-1 for i in range(max_val)]
   table[0] = 0
   v = [4, 6, 9]
   for i in range(1, max_val, 1):
      for k in range(3):
         j = v[k]
         if (i >= j and table[i - j] != -1):
            table[i] = max(table[i], table[i - j] + 1)
   return table
def max_summ(table, n):
   if (n < max_val):
      return table[n]
   else:
      t = int((n - max_val) / 4)+ 1
      return t + table[n - 4 * t]
n = 16
table = pre_calc()
print(max_summ(table, n))

Tìm số lượng tối đa các tổng hợp của một số trong Python

Ví dụ

Đầu vào

Đầu ra