División de un conjunto de números.

Question

Considera una lista de números que pueden tener valores de $1$ a $10$, y dos grupos que pueden contener un máximo de $100$ en total. Ahora, los números deben ser distribuidos entre estos dos grupos de manera que ninguno exceda $100$ en total. ¿Cuál es el valor total máximo de los números, de manera que siempre sea posible dividirlos en grupos sin exceder 100?

Sé que el valor máximo posible es 200, y he comenzado a eliminar casos eligiendo divisiones difíciles: como 22*9 + 2, que no se ajustará a 200.

Pero no sé cuál es el verdadero valor máximo.

Answer 1

Tenga en cuenta que si el elemento más pequeño es $k$ y el total es a lo sumo $201 - k$, entonces podemos ignorar este elemento, partir el resto y luego agregarlo al grupo con el total más pequeño, que necesariamente será como máximo $100 - k$. Por lo tanto, todos los totales hasta $191$ funcionan y también lo hace $192$ ya que para que ese sea el total, no todos los números pueden ser $10$.

Usando estas restricciones, buscar todas las posibilidades para $193$ en adelante es bastante fácil mediante una búsqueda por computadora. Según la salida, todo hasta $196$ se puede dividir, y hay $4$ listas con total $197$ que no se pueden dividir:

• $32 \times 6 + 5$
• $24 \times 8 + 5$
• $23 \times 8 + 7 + 6$
• $22 \times 8 + 3 \times 7$

El primer párrafo sugiere dos algoritmos voraces para encontrar una partición: considere los números de mayor a menor y colóquelos en la mitad que actualmente tiene (1) el total más bajo (2) el total más alto si cabe. El total más pequeño (1) que falla es $4 \times 10 + 17 \times 9 = 193$ (con las divisiones válidas $4 \times 10 + 6 \times 9$, $11 \times 9$ y $3 \times 10 + 7 \times 9$, $10 + 10 \times 9$). Similarmente, el total más alto (2) que falla es $3 \times 10 + 12 \times 9 + 7 \times 8 = 194$ (con divisiones válidas $1 \times 10 + 10 \times 9$, $2 \times 10 + 2 \times 9 + 7 \times 8$, etc).