コードの最適化 - 組み合わせの量

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個のアイデアを使用してください。

は、a[0], a[1], ..., a[j]という用語を使用してiのパーティション数に等しいとします。配列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
私があなただったら、私はn個のCを分割[i]を第一およびCをチェックします4/1 = [4] => integer count 1
4/2 = [2] =>整数カウンタが2になったとき[2]を1 + 1に分割する1がセットに含まれている場合
セットに3がある場合[1,2,3 ]、4/3を減算すると、1がセットに含まれていれば4-3 = 1が減算され、カウンタが増え、大きな結果が得られます。