dar que $ k+1 $enteros positivos $ A>a_1 \ge a_2 \ge \ldots \ge a_k $. Un subconjunto $ M \subseteq \lbrace 1,\ldots,k \rbrace $ se llama buena, si
i $ \sum_{m \in M} a_m \ge A $
(ii) propiedad (i) no tiene ningún subconjunto apropiado $ M' \subset M $.
¿Hay una forma eficiente (es decir, por ejemplo de orden $ k^d $ para algunas pequeñas $ d \in \mathbb{N} $) y decidir si existe un buen conjunto de $ M $ $ |M| \ge 3 $ o no?
Si la suma de cada par de elementos (con diferentes índices) de una secuencia de menos de $A$ que el algoritmo descrito en 2 se encuentra una buena secuencia con 3 o más elementos en el tiempo lineal, porque no se puede terminar con un uno o dos elementos.
Si $s_3$ es un buen larga con tres o más elementos, entonces no puede haber dos elementos que suma hasta un valor mayor o igual a $A.$
Si $s_1$ es una larga de $s$ $s_2$ es una larga de $s_1$ y, por tanto, una larga de $s$ $s_2$ es bueno con respecto a los $A$ $s$ si y sólo si $s_2$ es bueno con respecto a los $s_1$ $A.$
Definir $ss(s,i,A)$ como la larga de una secuencia $s$ tal que $a_k$ es en esta larga si $k=i$ o si $i \lt k$ $a_i+a_k<A.$
Si $s_2$ es un buen larga de una secuencia $s$ con respecto al $A$ $a_i$ es su elemento más grande, a continuación, $s_2$ es un buen larga de $ss(s,i,A)$ con respecto al $A$. Un buen larga de $ss(s,i,A)$ puede ser encontrado en el tiempo lineal, como se describe en el punto 3. Un buen larga de $ss(s,i,A)$ con respecto al $A$ debe tener tres o más elementos.
Ejemplo1
Si $s$ es la secuencia de las $8,8,7,6,1,1$ $A=9$ esto funciona de la siguiente manera: investigamos $$ss(s,1,9)=8$$ $$ss(s,3,9)=7,1,1$$ $$ss(s,4,9)=6,1,1$$ $$ss(s,5,9)=1,1$$
The first two have less than 3 elements and the third and the following one does not sum up to 9 or higher. So there is no good subsquence.
Example2
If $s$ is the sequence $8,8,7,6,2,2,1,1$ and $A=9$ esto funciona de la siguiente manera: investigamos $$ss(s,1,9)=8$$ $$ss(s,3,9)=7,1,1$$ $$ss(s,4,9)=6,2,2,1,1$$ $$ss(s,5,9)=2,2,1,1$$ $$ss(s,7,9)=1,1$$
Only the third one is of interest. We scan through $6,2,2,1,1$ from the beginning. We cannot drop $6$ but the first $2$ and the first $1$ and end with the good subsequence $6,2,1$
From this we construct the following algorithm that needs $O(k)$ time.
All numbers are integer. We have given $k$ que $$k \ge 3 \tag{1}$$ finita y ordenada de la secuencia de $a_1,\ldots, a_k$, por lo que $$a_1\ge a_2\ge\ldots\ge a_k \gt 0 \tag{2}$$ y un número $A$ tal que $$A \gt a_1$$
hemos creado \begin{align} &u:=1\\ &\text{while }(a_u+a_{k-1}\ge A) \text{ and } (u\lt k-2) \\ &\qquad u:=u+1 \\ \end{align} Ahora si $a_u+a_{k-1}<A$ entonces existe no $v$ tal que $a_u+a_v\ge A$ y por lo tanto no existe ninguna buena subconjunto con al menos $3$ elementos. El algoritmo terminará.
De lo contrario continúa:
\begin{align} &\text{tailsum}:=a_{k-1}+a_k\\ &v:=k-1\\ &\text{while }(u \lt v-1) \text{ and }a_u+a_{v-1} \lt A\\ &\qquad v:=v-1\\ &\qquad \text{tailsum}:=\text{tailsum}+a_{v}\\ \end{align}
ciclo invariante
$$\text{tailsum}=\sum_{t=v}^{k}a_t$$
\begin{align} &\text{while }(u\lt v-1) \text{ and } (a_u+\text{tailsum} \lt A)\\ &\qquad u:=u+1\\ &\qquad\text{while } (u \lt v-1) \text{ and } (a_u+a_{v-1} \lt A)\\ &\qquad\qquad v:=v-1\\ &\qquad\qquad\text{tailsum}:=\text{tailsum}+a_v\\ \end{align}
Nota tha $v$ ts disminuye, pero nunca se incrementan en este bucle. Sólo se puede decremente $k$ veces. Para este bloque se ejecuta en $O(k)$ del tiempo.
Si tenemos ahora $$a_u+\text{tailsum}\lt A$$ then $u=v-1$. No hemos encontrado un par (u,v) tal que $$a_u+\sum_{t=v}^k a_t<A$$ hasta ahora, y que no vamos a encontrar cuando nos disminución adicional de la $u$ porque esto disminuirá $v$, demasiado, y por lo tanto disminuir la suma de $a_u+\sum_{t=v}^k a_t.$ Así que no hay buen juego con tres o más elementos va a existir y el algoritmo terminará aquí.
Si el bucle termina con $a_u+\text{tailsum}\ge A$ $${u, v, v+1, \ldots, k}$$ will have a good subset and this will have $3$ o más elementos.
\begin{align} &\text{if } \text{tailsum} \lt A \text{ then}\\ &\qquad G:=\{u\}\\ &\qquad\text{sum}:=a_u+\text{tailsum}\\ &\text{else}\\ &\qquad G:=\{\}\\ &\qquad\text{sum}:=\text{tailsum}\\ &t=v\\ &\text{while } (t<=k)\\ &\qquad \text{if } \text{sum} - a_t \lt A \text{ then}\\ &\qquad\qquad G:=G\cup \{t\}\\ &\qquad\text{else}\\ &\qquad\qquad\text{sum}:=\text{sum}-a_t\\ &\qquad t=t+1\\ \end{align}
bucle de invariantes:$$\sum_{t\in G}a_t+\sum_{t=v}^k a_t=\text{sum}$$ $$\sum_{t\in G}a_t+\sum_{t=v}^k a_t \ge A$$ $$\sum_{t\in G\setminus \{r\}}a_t+\sum_{t=v}^k a_t \lt A,\; \forall r \in G$$
def find_good(a):
A=a[0] # python lists start with index 0
k=len(a)-1
if k<3:
return(None)
u=1
## Initialize u
while(a[u]+a[k-1]>=A) and (u<k-2):
u=u+1
if a[u]+a[k-1]>=A:
return(None)
## Initialize v
v=k-1
tailsum=a[k-1]+a[k]
while(a[u]+a[v-1]<A) and (u<v-1):
v=v-1
tailsum=tailsum+a[v]
# loop
while((u<v-1) and (a[u]+tailsum<A)):
u=u+1
while((u<v-1) and (a[u]+a[v-1]<A)):
v=v-1
tailsum=tailsum+a[v]
# decision
if ((a[u]+tailsum)<A):
# no solution exists
return(None)
# construction of a goot set:
if (tailsum<A):
G=[u]
sum=a[u]+tailsum
else:
G=[]
sum=0
t=v
while (t<=k):
if sum-a[t]<A:
G.append(t)
else:
sum=sum-a[t]
t=t+1
#prepare return value
H=[a[k] for k in G] # H is a[g1], a[g2],...
return(G, H)
Aquí hay un enlace al programa: https://repl.it/@miracle173/findgood2
Esta es mi segunda propuesta. Mi respuesta inicial fue demostrado falso, y pienso en la eliminación de la próxima semana. Porque esto es muy diferente, he decidido publicar una nueva respuesta en lugar de editar mi anterior. Si que es contraria a la política de la red, me disculpo de antemano.
Esto es bastante extensa, así que un tl;dr: yo creo que hay una manera de resolver el problema con un $k\log k$ ensayo. [EDIT]: ahora creo que esto se puede hacer en $\mathcal O(k)$. Originalmente, el $k\log k$ costo fue de una operación de ordenación que, de hecho, puede ser simplificado. Más detalles en la sección dedicada a la complejidad, después de explicar el principio del método.
Puedo presentar una caracterización de las subconjunto deseado y, a continuación, explicar el principio el algoritmo me derivan a partir de esa caracterización. Debido a que el algoritmo falla si utilizamos su ingenuo introducción, luego se explica cómo lidiar con el problema. Por último, me proporcionan algunos pseudo-código.
Reclamo: existe una buena subconjunto $M$ $\lvert M\rvert\ge 3$ si y sólo si hay dos índices de $i$ $j$ tal forma que:
Prueba: vamos a proceder por la doble implicación.
Deje $M$ un buen subconjunto de cardinalidad al menos 3. Deje $i<j$ ser su mínimo de dos índices. Por la condición (ii), $a_i+a_j< A$. Por la condición (i) tenemos $a_i+a_j+\sum_{l=j+1}^ka_l \ge \sum_{l\in M}a_l \ge A$. Por lo tanto, el mínimo de dos de los índices de $M$ satisfacen la propiedad.
Por el contrario, supongamos que hay dos índices de $i$ $j$ que satisfacen la propiedad. Inicializar $M=\{i,j\}$. Bucle por encima del índice $l$, a partir del valor de $j+1$$k$. Añadir índice $l$ $M$si la suma de los elementos en $M$ es estrictamente menor que $A$. Si la suma es mayor o igual a $A$, podemos parar. Porque hemos de añadir elementos, que son más pequeños y más pequeños, el resultado es $M$ va a ser buena. En otras palabras, cuando nosotros finalmente llegar a un subconjunto $M$ cuya suma es mayor que (o igual a) $A$, la condición (ii) también se cumplirá.
Esta equivalencia sugiere que se puede recorrer posible índices de $j$$2\le j\le k-1$, e intentar buscar algún índice $i$ que se ajusta al criterio. Es decir, dado un cierto índice $j$, podemos encontrar un índice de $i$ tal forma que:
Tenga en cuenta que $i<j$ implica $a_i\ge a_j$, lo $a_i$ también debe cumplir la desigualdad. Idealmente, me gustaría definir $b^-_j=\max\{ a_j;\ A-\sum_{l=j}^ka_l\}$ $b^+_j=A-a_j$ , para luego decir que basta con encontrar algún índice $i$ tal que $b^-_j\le a_i<b^+_j$. Que sin embargo no funciona debido a que $a_i\ge a_j$ no implica $i<j$. De hecho, algunos de los valores de $a_{i/j}$ puede ser repetido.
[EDIT]: Como alguien señaló en los comentarios, este problema también puede ser expresado como la búsqueda de $i$ $b^-_j\le a_i<b^+_j$ , pero luego te das cuenta de que $i=j$.
SI realmente teníamos equivalencia, podemos realizar una prueba para una buena subconjunto $M$, $\lvert M\rvert\ge 3$ mediante el uso de una lista ordenada. Primero eliminamos cualquier intervalo de $[b^-_j,b^+_j)$ que está vacío, en otras palabras, si $b^+_j\le b^-_j$, podemos olvidarnos de ese particular $j$ candidato. A continuación, seleccionamos todos los (restantes) $b^-_j$, $b^+_j$ y $a_i$, con el convenio que para valores iguales, $b^-_j$ es menor que $a_i$, y $a_i$ es menor que $b^+_j$. Podríamos ir más a la lista ordenada y:
[EDIT]: he cambiado la complejidad de la demanda lineal (anteriormente $k\log k$).
En general, la clasificación arbitraria de listas es una $k\log k$ proceso, por lo que el procedimiento anteriormente tendría $k\log k$ complejidad. Sin embargo, aquí las listas no son arbitrarias. En realidad tenemos que fusionar listas que ya están clasificados, y que se puede hacer en el tiempo lineal.
De hecho, el $a_i$ están disminuyendo, y por lo tanto $b^+_j=A-a_j$ es cada vez mayor. Debido a que el $a_i$'s son enteros positivos, la suma de $\sum_{l=j}^ka_l$ es estrictamente decreciente, y por lo tanto $A-\sum_{l=j}^ka_l$ es estrictamente creciente. De ello se desprende que $b^-_j$ es de un máximo entre dos secuencias monótonas y también pueden ser fácilmente combinados.
Estas observaciones también celebrar con los valores modificados $\hat a_i$, $\hat b_j^-$ y $\hat b^+_j$ que presento a continuación.
Para mi propuesta de método de trabajo, debemos obtener una manera de tener una equivalencia entre el$i<j$$a_i>a_j$. Debido a que estamos trabajando con números enteros, esto puede lograrse mediante la definición de nuevos valores de $\hat a_i$ que no son necesariamente enteros.
Si $a_i$ aparece sólo una vez, dejamos $\hat a_i=a_i$.
Si el valor de $a_i$ aparece varias veces, decir $n$ veces en los índices de $i_1<\ldots<i_m<\ldots<i_n$. Luego la dejamos $\hat a_{i_m}=a_i+\frac{m-1}n$. De este modo, obtener valores no enteros, con $$a_i+1 > \hat a_{i_1} >\ldots> \hat a_{i_m} >\ldots> \hat a_{i_n}=a_i$$ De ello se desprende que $i<j$ es equivalente a $\hat a_i>\hat a_j$.
[EDIT]: Tl;dr pequeño cambio en la definición de $\hat b^-_j$, de modo que mi reclamación 2 puede tener una correcta prueba. Que el cambio requiere una nueva notación $n_i$.
Para un índice $i$, vamos a $n_i$ ser el número de veces que el valor de $a_i$ aparece en la lista original (posiblemente $n_i=1$). Observe que $\frac 1{n_i}$ es la distancia entre valores consecutivos $\hat a_{i_m}$$\hat a_{i_{m+1}}$, cuando se $n_i\ge 2$.
A continuación, definimos $\hat b^-_j=\max\{ \hat a_j+\frac 1{2n_j};\ A-\sum_{l=j}^ka_l\}$ y $\hat b^+_j=A-a_j$. Observar que, independientemente del valor de $n_j$, tenemos $$\hat a_{j-1} > \hat a_j+\frac 1{2n_j} > \hat a_{j} $$
[EDIT]: la Reivindicación 2 se mantiene sin cambios, pero su prueba ha cambiado para reflejar el cambio en la definición.
Reivindicación 2: Tenemos $\hat b^-_j\le \hat a_i< \hat b_j^+$ si y sólo si
Prueba: Supongamos primero que $\hat b^-_j\le \hat a_i< \hat b^+_j$. Por definición de los diferentes términos que hemos $$ \hat a_i\ge\hat b^-_j\ge\hat a_j+\frac 1{2n_j}>\hat a_j $$ La parte que realmente nos interesa es $\hat a_i>\hat a_j$, ya que implica $i<j$. Tenemos nuestra primera condición. Para la segunda condición, observe que debido a que $A-\sum_{l=j}^ka_l$ es un número entero, podemos usar la función del suelo y preservar las desigualdades: \begin{align*} \hat b^-_j\le \hat a_i< \hat b^+_j &\implies A-\sum_{l=j}^ka_l\le \hat a_i< A-a_j\\ &\implies \left\lfloor A-\sum_{l=j}^ka_l\right\rfloor\le \lfloor\hat a_i\rfloor< A-a_j\\ &\implies A-\sum_{l=j}^ka_l\le a_i< A-a_j \end{align*} Por lo tanto, las dos condiciones se verifican.
Por el contrario, supongamos que $i<j$ y $A-\sum_{l=j}^ka_l\le a_i< A-a_j$. Porque $$A-\sum_{l=j}^ka_l\le a_i\le \hat a_i< a_i+1\le A-a_j=\hat b^+_j$$ tenemos $$A-\sum_{l=j}^ka_l\le \hat a_i<\hat b^+_j$$ Debido a $i<j$ sabemos que $$ \hat a_i\ge \hat a_{j-1}>\hat a_j +\frac 1{2n_j} $$ Combinado con lo anterior, podemos deducir $\hat b^-_j\le \hat a_i$. Las dos condiciones implican $\hat b^-_j\le \hat a_i<\hat b^+_j$, lo que concluye la prueba.
En este pseudo-código, b+_j denota $\hat b^+_j$, asimismo, b-_j es $\hat b^-_j$. También, a_i realidad denota $\hat a_i$.
Cómputo de los valores de $\hat a_i$ se puede hacer en el tiempo lineal wrt $k$.
Compute the various b+_j and b-_j //linear wrt k
Discard any pair b-_j/b+_j if b+_j <= b-j //forget about intervals with no solution
Sort the b+_j, b-_j and a_i in a list L //k log k
state = [0,...,0] //array of k values for interval status: 0=closed, 1=open
open_flag = 0 //counter value indicating if some interval is open
for x in L:
if x is an element of type b-_j: //open interval j
state[j] = 1
open_flag += 1
end if
if x is an element of type b+_j: //close interval j
state[j] = 0
open_flag -= 1
end if
if x is an element of type a_i: //check if an interval is open
if open_flag > 0:
return True or find a good pair i,j using the "state" array
end if
end if
end for //this loop was linear wrt the size of L, thus linear wrt k
return False //if we reach this point, we never found a good pair
Tenga en cuenta que si no nos preocupamos por encontrar un buen subconjunto, y sólo sobre su existencia, lo que no necesita preocuparse acerca de la matriz de estado.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
