Оптимизация кода - количество комбинаций

Question

Существует определенное число C (C - целое число) и дается список чисел (назовем его N, все числа в списке N являются целыми числами). Моя задача состоит в том, чтобы найти количество возможностей для представления C.

Например:

вход:

C = 4 

N = [1, 2] 

выход:

3 

Потому что:

4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 2 + 2 

Мой код работает очень хорошо для небольших чисел. Однако я понятия не имею, как я могу оптимизировать его, чтобы он работал и для больших целых чисел. Любая помощь будет оценена!

Существует мой код:

import numpy 
import itertools 
def amount(C): 
    N = numpy.array(input().strip().split(" "),int) 
    N = list(N) 
    N = sorted(N) 
    while C < max(N): 
     N.remove(max(N)) 
    res = [] 
    for i in range(1, C): 
     for j in list(itertools.combinations_with_replacement(N, i)): 
      res.append(sum(list(j))) 
    m = 0 
    for z in range (0, len(res)): 
     if res[z] == C: 
      m += 1 
    if N[0] == 1: 
     return m + 1 
    else: 
     return m 

Answer 1

Сложность вашего алгоритма O(len(a)^С). Чтобы решить эту задачу более эффективно, используйте идеи dynamic programming.

Предполагается, что dp[i][j] соответствует количеству разделов i с использованием условий a[0], a[1], ..., a[j]. Массив a не должен содержать дубликатов. Это решение работает в O(C * len(a)^2) раз.

def amount(c): 
    a = list(set(map(int, input().split()))) 

    dp = [[0 for _ in range(len(a))] for __ in range(c + 1)] 
    dp[0][0] = 1 

    for i in range(c): 
     for j in range(len(a)): 
      for k in range(j, len(a)): 
       if i + a[k] <= c: 
        dp[i + a[k]][k] += dp[i][j] 

    return sum(dp[c]) 

Answer 2

пожалуйста, проверьте этот первый: https://en.wikipedia.org/wiki/Combinatorics
также этот https://en.wikipedia.org/wiki/Number_theory
, если бы я тебя, я бы разделил с на п [я] первая и проверить гр не является номером из вашего примера: 4/1 = [4] => целочисленный счет 1
4/2 = [2] => целочисленный счетчик стал 2, затем разделил [2] на 1 + 1, если и только если 1 находится в наборе
что делать, если у вас есть 3 в комплекте [1,2,3 ], 4/3 просто вычесть 4-3 = 1, если 1 в наборе, счетчик увеличивается и для больших результатов я сделаю некоторое разбиение на основе набора