Python에서 숫자의 합성 합계의 최대 수 찾기

주어진 숫자 N이 있고 범위(1<=N<=10^9)에서 N을 가능한 가장 큰 합성 피합계 수의 합으로 나타내야 하고 이 가장 큰 숫자를 반환하고, 그렇지 않으면 분할을 찾을 수 없으면 -1을 반환합니다.

따라서 입력이 16과 같으면 출력은 4가 됩니다. 16은 4 + 4 + 4 + 4 또는 8 + 8로 쓸 수 있지만 (4 + 4 + 4 + 4)에는 최대 합이 있기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

max_val :=16
pre_calc() 함수를 정의합니다. 소요 시간
table :=max_val 크기 목록, 각 위치에 -1 저장
테이블[0] :=0
v :=[4, 6, 9]
범위 1에서 max_val까지의 i에 대해 1씩 증가, 수행
- 범위 0에서 2 사이의 k에 대해 수행
  - j :=v[k]
  - i>=j이고 table[i - j]가 -1이 아니면
    - table[i] :=table[i]의 최대값, table[i - j] + 1
반환 테이블
max_summ() 함수를 정의합니다. 이것은 테이블이 필요합니다. n
n
- 반환 테이블[n]
그렇지 않으면
- t :=((n - max_val) / 4) + 1의 정수
- 리턴 t + 테이블[n - 4 * t]
기본 방법에서 다음을 수행하십시오 -
테이블 :=pre_calc()
표시 max_summ(테이블, 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))