Encontrar todas las combinaciones que suma hasta un específico número dado limita

Question

Esta es una continuación de este problema. Encontrar todas las combinaciones que se pueden resumir en un número específico

Creo que de los siguientes valores.

T = Target // The value to target. eg 100
I = Items // Number of items that makes T. eg 5

Ahora No sólo como la anterior pregunta, quiero los números para ser aumentado por un intervalo de paso (en lugar de $1$) como $2$, $5$, $10$, etc. El valor de paso es $S$ (por ejemplo: $2$, $5$, $10$).

También se $H_i$ le dirá cuál es el máximo valor específico que voy a llegar y $L_i$ va a decir lo que es el valor más bajo específicas voy a comenzar con.

Por ejemplo:

$T = 100$, $I = 3$, $S = 2$
$L_1 = 10$, $L_2 = 20$, $L_3 = 0$
$H_1 = 100$, $H_2 = 80$, $H_3 = 80$

Si encima es el valor, toda la combinación tendrá un aspecto como el de abajo

010, 020, 070
010, 022, 068   ;Always Increasing / Decrease by 2 since S = 2
010, 024, 066
010, 026, 064
.....           ;After many  combinations
010, 080, 000
012, 020, 068
012, 022, 066
.....
.....
080, 018, 002
080, 020, 000   

Aunque $H_1=100$, $I_1$ no puede llegar a $100$ desde $L_2=20$.

¿Cuál es la fórmula para encontrar el número si la combinación podemos llegar con si $T$, $I$, $S$, $H_i$ e $L_i$ son dados? Incluso la solución de programación es suficiente.

Answer 1

Basado en la información adicional aportada en los comentarios de arriba, el problema puede enunciarse como:

Dado números enteros no negativos $T, I, S$ tal que $S \mid T$. Encontrar el número de enteros soluciones a $$\sum_{k = 1}^I x_k = T$$ con las limitaciones de $$L_k \leqslant x_k \leqslant H_k,\ S \mediados de x_k, \quad k = 1, \cdots, me$$ donde $L_k$'s y $H_k$'s se dan números enteros no negativos tales que $S \mid L_k$, $S \mid H_k$, e $L_k \leqslant H_k$.

Definir $T' = \dfrac{1}{S} \left( T - \sum\limits_{k = 1}^I L_k \right)$, $M_k = \dfrac{1}{S} (H_k - L_k)$, $y_k = \dfrac{1}{S} (x_k - L_k)$, entonces el problema es equivalente a encontrar el número de enteros soluciones a $$\sum_{k = 1}^I y_k = T'$$ con las limitaciones de $$0 \leqslant y_k \leqslant M_k. \quad k = 1, \cdots, me$$

Now define $f(0, 0) = 1$, $f(0, m) = 0\ (m ≠ 0)$, and $f(n, m)\ (1 \leqslant n \leqslant I)$ as the number of integer solutions to $$\sum_{k = 1}^n y_k = m$$ con las limitaciones de $$0 \leqslant y_k \leqslant M_k. \quad k = 1, \cdots, n$$ Fijo $n$, desde el $0 \leqslant y_n \leqslant M_n$, luegode $$f(n, m) = \sum_{k = 0}^{M_n} f(n - 1, m - k).$$ Tenga en cuenta que el caso de que $n = 1$ está incluido. Definir $$g(n, m) = \begin{cases} \sum\limits_{k = 0}^m f(n, k); & m \geqslant 0\\ 0; & m < 0 \end{casos},$$ entonces $$\begin{cases} f(n, m) = g(n - 1, m) - g(n - 1, m - M_n - 1)\\ g(n, m) = g(n, m - 1) + f(n, m) \end{casos}, \quad (n \geqslant 1,\ m \geqslant 0)$$ o $$\begin{cases} f(n, m) = g(n - 1, m)\ (0 \leqslant m \leqslant M_n)\\ f(n, m) = g(n - 1, m) - g(n - 1, m - M_n - 1)\ (m > M_n)\\ g(n, 0) = 1\\ g(n, m) = g(n, m - 1) + f(n, m)\ (m \geqslant 1) \end{casos}$$

The code is showed below (with some optimization).

tmp = 0;
for(i = 1; i <= I; i++) {
    tmp += L[i];
    M[i] = (H[i] - L[i]) / S;
}
N = (T - tmp) / S;  //T' is renamed as N

sort(M);    //Ascending order

i_0 = 0;
while(!M[++i_0]);   //M[i] = 0 implies y[i] = 0

f[i_0 - 1][i_0 - 1] = 1;
for(i = i_0; i <= N; i++) f[i_0 - 1][i] = 0;
for(i = i_0; i <= N; i++) g[i_0 - 1][i] = 1;

for(i = i_0; i <= I; i++) {
    for(j = 0; j <= M[i] && j <= N; j++)
        f[i][j] = g[i - 1][j];
    for(j = M[i] + 1; j <= N; j++)
        f[i][j] = g[i - 1][j] - g[i - 1][j - M[i] - 1];

    g[i][0] = 1;
    for(j = 1; j <= N; j++)
        g[i][j] = g[i][j - 1] + f[i][j];
}

The time complexity is approximately $S(TIS^{-1})$.

Answer 2

Aquí podemos calcular OP ejemplo de uso de una generación de la función de enfoque. A continuación, se derivan de una manera similar a una fórmula general de que la quería número pueden ser obtenidos manualmente, al menos para valores pequeños de a$I$.

Consideramos $T=100, I=3, S=2$ y la de los pares de $$(L_j,H_j)\in\{(10,100),(20,80),(0,80)\}.$$

Es conveniente utilizar el coeficiente de operador $[x^n]$ para denotar el coeficiente de $x^n$ en una serie. Obtenemos

$$\begin{align*} \color{blue}{[x^{100}]}&\color{blue}{\left(x^{10}+x^{12}+\cdots+x^{100}\right)\left(x^{20}+x^{22}+\cdots+x^{80}\right)\left(x^0+x^2+\cdots+x^{80}\right)}\tag{1}\\ &=[x^{100}]x^{10}\left(\sum_{j=0}^{45}x^{2j}\right)x^{20}\left(\sum_{j=0}^{30}x^{2j}\right)\left(\sum_{j=0}^{40}x^{2j}\right)\tag{2}\\ &=[x^{70}]\frac{1-x^{92}}{1-x^2}\cdot\frac{1-x^{62}}{1-x^2}\cdot\frac{1-x^{82}}{1-x^2}\tag{3}\\ &=[x^{70}]\frac{1-x^{62}}{(1-x^2)^3}\tag{4}\\ &=[x^{70}]\left(1-x^{62}\right)\sum_{j=0}^\infty\binom{-3}{j}\left(-x^2\right)^j\tag{5}\\ &=\left([x^{70}]-[x^8]\right)\sum_{j=0}^{\infty}\binom{j+2}{2}x^{2j}\tag{6}\\ &=\binom{37}{2}-\binom{6}{2}\tag{7}\\ &\,\,\color{blue}{=651} \end{align*}$$

Comentario:

• En (1) que codifican para cada una de las tres variables de todas las posibilidades en términos de generación de funciones.

• En (2) nos factor común de los términos y el uso de la sigma símbolo para un más compacto de la notación.

• En (3) aplicamos la serie geométrica finita fórmula y utilizamos la fórmula $[x^p]x^qA(x)=[x^{p-q}]A(x)$.

• En (4) se calcula el numerador de (3) omitiendo todos los poderes mayor que $70$ ya que no contribuyen a $[x^{70}]$.

• En (5) se aplica el binomio de expansión de la serie.

• En (6) se aplica el binomio identidad $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$. Utilizamos la linealidad del coeficiente de operador y aplicar de nuevo la fórmula, tal como hicimos en (3).

• En (7) seleccionamos los coeficientes en consecuencia.

Ahora podemos derivar una fórmula general, de forma similar a como lo hicimos en el ejemplo concreto de arriba.

Obtenemos $$\begin{align*} \color{blue}{[x^T]}&\color{blue}{\prod_{j=1}^I\left(x^{L_j}+x^{L_j+S}+\cdots+x^{L_j+S\left\lfloor \frac{H_j-L_j}{S}\right\rfloor}\right)}\\ &=[x^T]x^{\sum_{j=1}^{I}{L_j}}\prod_{j=1}^I\left(1+x^S+\cdots+x^{S\left\lfloor \frac{H_j-L_j}{S}\right\rfloor}\right)\\ &=[x^T]x^{\sum_{j=1}^{I}{L_j}}\prod_{j=1}^I\sum_{k=0}^{\left\lfloor \frac{H_j-L_j}{S}\right\rfloor}x^{k\cdot S}\\ &=[x^T]x^{\sum_{j=1}^{I}{L_j}}\prod_{j=1}^l \frac{1-x^{S\left(\left\lfloor \frac{H_j-L_j}{S}\right\rfloor+1\right)}}{1-x^S}\\ &=[x^T]x^{\sum_{j=1}^{I}{L_j}}\prod_{j=1}^l \left(1-x^{S\left(\left\lfloor \frac{H_j-L_j}{S}\right\rfloor+1\right)}\right)\sum_{j=0}^\infty \binom{-I}{j}(-x)^S\\ &\,\,\color{blue}{=[x^T]x^{\sum_{j=1}^{I}{L_j}}\prod_{j=1}^l \left(1-x^{S\left(\left\lfloor \frac{H_j-L_j}{S}\right\rfloor+1\right)}\right)\sum_{j=0}^\infty\binom{I+j-1}{I-1}x^S} \end{align*}$$ virtud de la cual la última línea corresponde a (6).