¿Cómo puede generar el conjunto más pequeño de números enteros tales que las sumas cubren un conjunto dado?

Question

Tengo un conjunto de enteros positivos S. quiero generar un conjunto de enteros positivos en T de tal manera que cada miembro de S es la suma de la combinación de algunos de los miembros de la T. estoy buscando la más pequeña posible, T.

I. e. Dado $S = \{x|x \in \Bbb N\}$, generan la más pequeña posible, $T = \{y|y \in \Bbb N\}$ tal que para cada una de las $x$ $S$ existe un $K \subset T$ donde $x = \sum_{y\in K} y$

Esta es una aplicación del mundo real. Una solución que está cerca de la óptima es lo suficientemente bueno. El tamaño de $S$ ~$2^{30}$

¿Este problema tiene un nombre conocido? No estoy llegando a ningún lado con google. Puede que me apunte en la dirección correcta?

Answer 1

Generar $T$ por etapas. Decir $A=\{a_1<a_2<a_3<\dots\}$. En la etapa $1$, puesto $a_1\in T$. En la etapa $2$, puesto $a_2\in T$. En el inicio de la etapa $n$, tenemos una aproximación a $T$. Si $a_n$ es la suma de los distintos elementos de esta aproximación, hemos terminado con esta etapa y pasar a la siguiente. De lo contrario, agregue $a_n\in T$, y esto concluye la etapa de $n$. En cada etapa se están agregando elementos sólo si son necesarios. El conjunto que llegar a la final es el "más pequeño" $T$ usted requiere. Tenga en cuenta que pequeñez aquí está asumiendo $T\subset S$. De lo contrario, no puede ser un conjunto más pequeño. Por ejemplo, si $S=\{1,3\}$ $T_1=S$ $T_2=\{1,2\}$ trabajo y se $\subseteq$-incomparable.