Tienes un montón de cajas pesadas y quieres apilarlas en la menor cantidad de pilas posibles. El problema es que no puede apilar más cajas en una caja de las que puede soportar, por lo que las cajas más pesadas deben ir en la parte inferior de una pila.

El reto

Entrada : Una lista de pesos de cajas, en kg enteros.

Salida : una lista de listas que describen las pilas de cajas. Esto debe usar la menor cantidad de pilas posibles para la entrada. Para ser una pila válida, el peso de cada caja en la pila debe ser mayor o igual a la suma del peso de todas las cajas que se encuentran arriba.

Ejemplos de pilas válidas

(En orden de abajo hacia arriba)

• [3]
• [1, 1]
• [3, 2, 1]
• [4, 2, 1, 1]
• [27, 17, 6, 3, 1]
• [33, 32, 1]
• [999, 888, 99, 11, 1]

Ejemplos de pilas inválidas

(En orden de abajo hacia arriba)

• [1, 2]
• [3, 3, 3]
• [5, 5, 1]
• [999, 888, 777]
• [4, 3, 2]
• [4321, 3000, 1234, 321]

Ejemplos de casos de prueba

1

IN: [1, 2, 3, 4, 5, 6, 9, 12]
OUT: [[12, 6, 3, 2, 1], [9, 5, 4]]

2

IN: [87, 432, 9999, 1234, 3030]
OUT: [[9999, 3030, 1234, 432, 87]]

3

IN: [1, 5, 3, 1, 4, 2, 1, 6, 1, 7, 2, 3]
OUT: [[6, 3, 2, 1], [7, 4, 2, 1], [5, 3, 1, 1]]

4 4

IN: [8, 5, 8, 8, 1, 2]
OUT: [[8, 8], [8, 5, 2, 1]]

Reglas y supuestos

• Se aplican las reglas estándar de E / S y las lagunas prohibidas
• Use cualquier formato conveniente para E / S
  • Las pilas pueden describirse de arriba a abajo o de abajo hacia arriba, siempre y cuando sea consistente.
  • El orden de las pilas (en lugar de las cajas dentro de esas pilas) no importa.
  • También puede tomar cuadros de entrada como una lista clasificada previamente. El orden no es particularmente importante para la entrada, siempre que el problema general no se resuelva con la clasificación en sí.
• Si hay más de una configuración óptima de pilas, puede generar cualquiera de ellas
• Puede suponer que hay al menos una caja y que todas las cajas pesan al menos 1 kg
• Debe soportar pesos de hasta 9.999 kg, como mínimo.
• Debe admitir hasta 9,999 cajas en total, como mínimo.
• Las cajas con el mismo peso no se pueden distinguir, por lo que no es necesario anotar en qué caja se utilizó.

¡Feliz golf! ¡Buena suerte!

Jalea , 19 bytes

Œ!ŒṖ€ẎṖÄ>ḊƲ€¬ȦƊƇLÞḢ

Pruébalo en línea!

Obvio -3 gracias a Nick Kennedy ...

De arriba hacia abajo.

Explicación:

Œ!ŒṖ€ẎṖÄ>ḊƲ€¬ȦƊƇLÞḢ  Arguments: S (e.g. [1, 2, 3, 4, 5])
Œ!                   Permutations (e.g. [..., [4, 1, 5, 2, 3], ...])
    €                Map link over left argument (e.g. [..., [..., [[4, 1], [5], [2, 3]], ...], ...])
  ŒṖ                  Partitions (e.g. [..., [[4, 1], [5], [2, 3]], ...])
     Ẏ               Concatenate elements (e.g. [..., ..., [[4, 1], [5], [2, 3]], ..., ...])
               Ƈ     Filter by link (e.g. [..., [[1, 3], [2], [4], [5]], ...])
              Ɗ       Create >=3-link monadic chain (e.g. [[1], [], [0]])
           €           Map link over left argument (e.g. [[1], [], [0]])
          Ʋ             Create >=4-link monadic chain (e.g. [1])
      Ṗ                  Remove last element (e.g. [4])
       Ä                 Cumulative sum (e.g. [4])
         Ḋ               [Get original argument] Remove first element (e.g. [1])
        >                Greater than (vectorizes) (e.g. [1])
            ¬          Logical NOT (vectorizes) (e.g. [[0], [], [1]])
             Ȧ         Check if non-empty and not containing zeroes after flattening (e.g. 0)
                 Þ   Sort by link (e.g. [[[1, 2, 3], [4, 5]], ..., [[5], [4], [3], [2], [1]]])
                L     Length (e.g. 4)
                  Ḣ  Pop first element (e.g. [[1, 2, 3], [4, 5]])

JavaScript (Node.js),  139122116  bytes

Espera la entrada ordenada en orden ascendente.

f=(A,s=[],[n,...a]=A,r)=>n?s.some((b,i,[...c])=>n<eval(b.join`+`)?0:f(A,c,a,c[i]=[n,...b]))?S:r?0:f(A,[...s,[]]):S=s

Pruébalo en línea!

Comentado

f = (                        // f is a recursive function taking:
  A,                         //   A[] = input array
  s = [],                    //   s[] = list of stacks, initially empty
  [n,                        //   n   = next weight to process
      ...a] = A,             //   a[] = array of remaining weights
  r                          //   r   = recursion flag
) =>                         //
  n ?                        // if n is defined:
    s.some((b, i,            //   for each stack b[] at position i in s[],
                  [...c]) => //   using c[] as a copy of s[]:
      n < eval(b.join`+`) ?  //     if n is not heavy enough to support all values in b[]:
        0                    //       abort
      :                      //     else:
        f(                   //       do a recursive call:
          A, c, a,           //         using A[], c[] and a[]
          c[i] = [n, ...b]   //         with n prepended to c[i]
        )                    //       end of recursive call
    ) ?                      //   end of some(); if successful:
      S                      //     return S[]
    :                        //   else:
      r ?                    //     if this is a recursive call:
        0                    //       do nothing
      :                      //     else:
        f(A, [...s, []])     //       try again with an additional stack
  :                          // else:
    S = s                    //   success: save the solution in S[]

Python 3.8 (prelanzamiento) , 178 bytes

f=lambda b,s=[[]]:(a for i in range(len(s))if b[0]>=sum(s[i])for a in f(b[1:],s[:i]+[[b[0]]+s[i]]+s[i+1:]+[[]]))if b else[s]
g=lambda a:(c:=sorted(f(a),key=len)[0])[:c.index([])]

Pruébalo en línea!

Ahora funciona en todas las entradas posibles. (Se agota el tiempo de espera en TIO con más de diez cuadros, pero calcula una respuesta correcta)