定数の組み合わせの数

Question

nの整数のリストL1,L2,...,Lnと整数Sが与えられたとします。

j1,j2,...,jnのようなインデックスの組み合わせを効率的に数える方法を探しています（L1[j1]+L2[j2]+...+Ln[jn] = S）。

たとえば、L1=[0,1,1,2], L2=[0,1], L3=[0,1,2,3,3]とS=4とします。 はその後、可能な組み合わせは、すなわち私が探しています答えは10ある

0+1+3 
0+1+3 
1+0+3 
1+0+3 
1+1+2 
1+0+3 
1+0+3 
1+1+2 
2+0+2 
2+1+1 

です。

Answer 1

DPで解決できます。複雑さ：O（nS）。

Count(i,s) = \sum_j=0..s Count(i-1,j) * Number of elements in list i with value (s-j) 

Answer 2

この問題はNP完全です。あなたは、いくつかの余分な性質を持っている場合は、

1）ブルートフォースそれは

または、（関与総和は、例えば、小さい）あなたも

が

2）を取得するには、動的プログラミングを使用し検討することができpseudopolinomialアルゴリズム。